@inproceedings{185,
abstract = {We resolve in the affirmative conjectures of A. Skopenkov and Repovš (1998), and M. Skopenkov (2003) generalizing the classical Hanani-Tutte theorem to the setting of approximating maps of graphs on 2-dimensional surfaces by embeddings. Our proof of this result is constructive and almost immediately implies an efficient algorithm for testing whether a given piecewise linear map of a graph in a surface is approximable by an embedding. More precisely, an instance of this problem consists of (i) a graph G whose vertices are partitioned into clusters and whose inter-cluster edges are partitioned into bundles, and (ii) a region R of a 2-dimensional compact surface M given as the union of a set of pairwise disjoint discs corresponding to the clusters and a set of pairwise disjoint "pipes" corresponding to the bundles, connecting certain pairs of these discs. We are to decide whether G can be embedded inside M so that the vertices in every cluster are drawn in the corresponding disc, the edges in every bundle pass only through its corresponding pipe, and every edge crosses the boundary of each disc at most once.},
author = {Fulek, Radoslav and Kynčl, Jan},
isbn = {978-3-95977-066-8},
location = {Budapest, Hungary},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Hanani-Tutte for approximating maps of graphs}},
doi = {10.4230/LIPIcs.SoCG.2018.39},
volume = {99},
year = {2018},
}
@inproceedings{186,
abstract = {A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The ℤ2-genus of a graph G is the minimum g such that G has an independently even drawing on the orientable surface of genus g. An unpublished result by Robertson and Seymour implies that for every t, every graph of sufficiently large genus contains as a minor a projective t × t grid or one of the following so-called t-Kuratowski graphs: K3, t, or t copies of K5 or K3,3 sharing at most 2 common vertices. We show that the ℤ2-genus of graphs in these families is unbounded in t; in fact, equal to their genus. Together, this implies that the genus of a graph is bounded from above by a function of its ℤ2-genus, solving a problem posed by Schaefer and Štefankovič, and giving an approximate version of the Hanani-Tutte theorem on orientable surfaces.},
author = {Fulek, Radoslav and Kynčl, Jan},
location = {Budapest, Hungary},
pages = {401 -- 4014},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{The ℤ2-Genus of Kuratowski minors}},
doi = {10.4230/LIPIcs.SoCG.2018.40},
volume = {99},
year = {2018},
}
@article{793,
abstract = {Let P be a finite point set in the plane. A cordinary triangle in P is a subset of P consisting of three non-collinear points such that each of the three lines determined by the three points contains at most c points of P . Motivated by a question of Erdös, and answering a question of de Zeeuw, we prove that there exists a constant c > 0such that P contains a c-ordinary triangle, provided that P is not contained in the union of two lines. Furthermore, the number of c-ordinary triangles in P is Ω(| P |). },
author = {Fulek, Radoslav and Mojarrad, Hossein and Naszódi, Márton and Solymosi, József and Stich, Sebastian and Szedlák, May},
issn = {09257721},
journal = {Computational Geometry: Theory and Applications},
pages = {28 -- 31},
publisher = {Elsevier},
title = {{On the existence of ordinary triangles}},
doi = {10.1016/j.comgeo.2017.07.002},
volume = {66},
year = {2017},
}
@article{794,
abstract = {We show that c-planarity is solvable in quadratic time for flat clustered graphs with three clusters if the combinatorial embedding of the underlying graph is fixed. In simpler graph-theoretical terms our result can be viewed as follows. Given a graph G with the vertex set partitioned into three parts embedded on a 2-sphere, our algorithm decides if we can augment G by adding edges without creating an edge-crossing so that in the resulting spherical graph the vertices of each part induce a connected sub-graph. We proceed by a reduction to the problem of testing the existence of a perfect matching in planar bipartite graphs. We formulate our result in a slightly more general setting of cyclic clustered graphs, i.e., the simple graph obtained by contracting each cluster, where we disregard loops and multi-edges, is a cycle.},
author = {Fulek, Radoslav},
journal = {Computational Geometry: Theory and Applications},
pages = {1 -- 13},
publisher = {Elsevier},
title = {{C-planarity of embedded cyclic c-graphs}},
doi = {10.1016/j.comgeo.2017.06.016},
volume = {66},
year = {2017},
}
@article{795,
abstract = {We introduce a common generalization of the strong Hanani–Tutte theorem and the weak Hanani–Tutte theorem: if a graph G has a drawing D in the plane where every pair of independent edges crosses an even number of times, then G has a planar drawing preserving the rotation of each vertex whose incident edges cross each other evenly in D. The theorem is implicit in the proof of the strong Hanani–Tutte theorem by Pelsmajer, Schaefer and Štefankovič. We give a new, somewhat simpler proof.},
author = {Fulek, Radoslav and Kynčl, Jan and Pálvölgyi, Dömötör},
issn = {10778926},
journal = {Electronic Journal of Combinatorics},
number = {3},
publisher = {International Press},
title = {{Unified Hanani Tutte theorem}},
volume = {24},
year = {2017},
}