License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2018.40
URN: urn:nbn:de:0030-drops-87539
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8753/
Go to the corresponding LIPIcs Volume Portal

Fulek, Radoslav ; Kyncl, Jan

The Z_2-Genus of Kuratowski Minors

pdf-format:
LIPIcs-SoCG-2018-40.pdf (0.5 MB)

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 Z_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 x t grid or one of the following so-called t-Kuratowski graphs: K_{3,t}, or t copies of K_5 or K_{3,3} sharing at most 2 common vertices. We show that the Z_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 Z_2-genus, solving a problem posed by Schaefer and Stefankovic, and giving an approximate version of the Hanani-Tutte theorem on orientable surfaces.

BibTeX - Entry

@InProceedings{fulek_et_al:LIPIcs:2018:8753,
  author =	{Radoslav Fulek and Jan Kyncl},
  title =	{{The Z_2-Genus of Kuratowski Minors}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{40:1--40:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Bettina Speckmann and Csaba D. T{\'o}th},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8753},
  URN =		{urn:nbn:de:0030-drops-87539},
  doi =		{10.4230/LIPIcs.SoCG.2018.40},
  annote =	{Keywords: Hanani-Tutte theorem, genus of a graph, Z_2-genus of a graph, Kuratowski graph}
}

Keywords: Hanani-Tutte theorem, genus of a graph, Z_2-genus of a graph, Kuratowski graph
Collection: 34th International Symposium on Computational Geometry (SoCG 2018)
Issue Date: 2018
Date of publication: 08.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI