The ℤ2-Genus of Kuratowski minors Conference Paper


Author(s): Fulek, Radoslav; Kynčl, Jan
Title: The ℤ2-Genus of Kuratowski minors
Title Series: Leibniz International Proceedings in Information, LIPIcs
Affiliation IST Austria
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.
Keywords: computational geometry; Graph theory; Computation theory; Hanani-Tutte theorem; Graph G; Genus of a graph; Kuratowski graph; Z2-genus of a graph; Kuratowski; Orientable surfaces
Conference Title: SoCG: Symposium on Computational Geometry
Volume: 99
Conference Dates: June 11 - 14, 2018
Conference Location: Budapest, Hungary
ISBN: 18688969 (ISSN); 9783959770668 (ISBN)
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik  
Date Published: 2018-06-11
Start Page: 401
End Page: 4014
DOI: 10.4230/LIPIcs.SoCG.2018.40
Open access: yes (repository)
IST Austria Authors
  1. Radoslav Fulek
    14 Fulek
Related IST Austria Work