Author(s):

Fulek, Radoslav; Kynčl, Jan

Title: 
The ℤ2Genus 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 ℤ2genus 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 socalled tKuratowski graphs: K3, t, or t copies of K5 or K3,3 sharing at most 2 common vertices. We show that the ℤ2genus 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 ℤ2genus, solving a problem posed by Schaefer and Štefankovič, and giving an approximate version of the HananiTutte theorem on orientable surfaces.

Keywords: 
computational geometry; Graph theory; Computation theory; HananiTutte theorem; Graph G; Genus of a graph; Kuratowski graph; Z2genus 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  LeibnizZentrum für Informatik

Date Published:

20180611

Start Page: 
401

End Page:

4014

DOI: 
10.4230/LIPIcs.SoCG.2018.40

Open access: 
yes (repository) 