Zuzana Patáková

activity

20162024

most citedA Direct Proof of the Strong Hanani-Tutte Theorem on the Projective Plane

1 citations · 1 across the 3 of their papers we have counts for

collaborators

4 papers

math.CO2024

Covering points by hyperplanes and related problems

Zuzana Patáková, Micha Sharir

For a set $P$ of $n$ points in $R^{d}$ , for any $d \geq 2$ , a hyperplane $h$ is called $k$ -rich with respect to $P$ if it contains at least $k$ points of $P$ . Answering and gen…

math.CO2017

Shellability is NP-complete

Xavier Goaoc, Pavel Paták, Zuzana Patáková +2

We prove that for every $d \geq 2$ , deciding if a pure, $d$ -dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Dan…

math.CO2016

On Generalized Heawood Inequalities for Manifolds: a van Kampen--Flores-type Nonembeddability Result

Xavier Goaoc, and Isaac Mabillard, Pavel Paták +3

The fact that the complete graph $K_{5}$ does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood proble…

cs.CG2016★ 1 cited

A Direct Proof of the Strong Hanani-Tutte Theorem on the Projective Plane

Éric Colin de Verdière, Vojtěch Kaluža, Pavel Paták +2

We reprove the strong Hanani-Tutte theorem on the projective plane. In contrast to the previous proof by Pelsmajer, Schaefer and Stasi, our method is constructive and does not rely…