The ℤ2-Genus of Kuratowski minors

R. Fulek, J. Kynčl, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.

Conference Paper | Published | English
Author
Department
Series Title
LIPIcs
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.
Publishing Year
Volume
99
Page
401 - 4014
Conference
SoCG: Symposium on Computational Geometry
Conference Location
Dagstuhl, Germany
IST-REx-ID

Cite this

Fulek R, Kynčl J. The ℤ2-Genus of Kuratowski minors. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPIcs.SoCG.2018.40
Fulek, R., & Kynčl, J. (2018). The ℤ2-Genus of Kuratowski minors (Vol. 99). Presented at the SoCG: Symposium on Computational Geometry, Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2018.40
Fulek, Radoslav, and Jan Kynčl. “The ℤ2-Genus of Kuratowski Minors,” Vol. 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.40.
R. Fulek and J. Kynčl, “The ℤ2-Genus of Kuratowski minors,” presented at the SoCG: Symposium on Computational Geometry, Dagstuhl, Germany, 2018, vol. 99.
Fulek R, Kynčl J. 2018. The ℤ2-Genus of Kuratowski minors. SoCG: Symposium on Computational Geometry vol. 99.
Fulek, Radoslav, and Jan Kynčl. The ℤ2-Genus of Kuratowski Minors. Vol. 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPIcs.SoCG.2018.40.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar