Document Open Access Logo

The Z_2-Genus of Kuratowski Minors

Authors Radoslav Fulek, Jan Kyncl

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.40.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Radoslav Fulek
Jan Kyncl

Cite As Get BibTex

Radoslav Fulek and Jan Kyncl. The Z_2-Genus of Kuratowski Minors. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 40:1-40:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.40

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.

Subject Classification

Keywords
  • Hanani-Tutte theorem
  • genus of a graph
  • Z_2-genus of a graph
  • Kuratowski graph

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Joseph Battle, Frank Harary, Yukihiro Kodama, and J. W. T. Youngs. Additivity of the genus of a graph. Bull. Amer. Math. Soc., 68:565-568, 1962. URL: http://dx.doi.org/10.1090/S0002-9904-1962-10847-7.
  2. Thomas Böhme, Ken-ichi Kawarabayashi, John Maharry, and Bojan Mohar. K_3,k-minors in large 7-connected graphs. Preprint available at http://preprinti.imfm.si/PDF/01051.pdf, 2008.
  3. Thomas Böhme, Ken-ichi Kawarabayashi, John Maharry, and Bojan Mohar. Linear connectivity forces large complete bipartite minors. J. Combin. Theory Ser. B, 99(3):557-582, 2009. URL: http://dx.doi.org/10.1016/j.jctb.2008.07.006.
  4. André Bouchet. Orientable and nonorientable genus of the complete bipartite graph. J. Combin. Theory Ser. B, 24(1):24-33, 1978. URL: http://dx.doi.org/10.1016/0095-8956(78)90073-4.
  5. G. Cairns and Y. Nikolayevsky. Bounds for generalized thrackles. Discrete Comput. Geom., 23(2):191-206, 2000. URL: http://dx.doi.org/10.1007/PL00009495.
  6. R. Christian, R. B. Richter, and G. Salazar. Embedding a graph-like continuum in some surface. J. Graph Theory, 79(2):159-165, 2015. URL: http://dx.doi.org/10.1002/jgt.21823.
  7. Éric Colin de Verdière, Vojtěch Kaluža, Pavel Paták, Zuzana Patáková, and Martin Tancer. A direct proof of the strong Hanani-Tutte theorem on the projective plane. J. Graph Algorithms Appl., 21(5):939-981, 2017. URL: http://dx.doi.org/10.7155/jgaa.00445.
  8. D. de Caen. The ranks of tournament matrices. Amer. Math. Monthly, 98(9):829-831, 1991. URL: http://dx.doi.org/10.2307/2324270.
  9. R. W. Decker, H. H. Glover, and J. P. Huneke. Computing the genus of the 2-amalgamations of graphs. Combinatorica, 5(4):271-282, 1985. URL: http://dx.doi.org/10.1007/BF02579241.
  10. J. R. Fiedler, J. P. Huneke, R. B. Richter, and N. Robertson. Computing the orientable genus of projective graphs. J. Graph Theory, 20(3):297-308, 1995. URL: http://dx.doi.org/10.1002/jgt.3190200305.
  11. R. Fulek and J. Kynčl. Counterexample to an extension of the hanani-tutte theorem on the surface of genus 4. Submitted, https://arxiv.org/abs/1709.00508, 2017.
  12. R. Fulek and J. Kynčl. The ℤ₂-genus of kuratowski minors. Manuscript, , 2018. Google Scholar
  13. Haim Hanani. Über wesentlich unplättbare Kurven im drei-dimensionalen Raume. Fundamenta Mathematicae, 23:135-142, 1934. Google Scholar
  14. Allen Hatcher. Algebraic topology. Cambridge University Press, Cambridge, 2002. Google Scholar
  15. D. J. Kleitman. A note on the parity of the number of crossings of a graph. J. Combinatorial Theory Ser. B, 21(1):88-89, 1976. Google Scholar
  16. Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 2001. Google Scholar
  17. Michael J. Pelsmajer, Marcus Schaefer, and Despina Stasi. Strong Hanani-Tutte on the projective plane. SIAM J. Discrete Math., 23(3):1317-1323, 2009. URL: http://dx.doi.org/10.1137/08072485X.
  18. Michael J. Pelsmajer, Marcus Schaefer, and Daniel Štefankovič. Removing even crossings on surfaces. European J. Combin., 30(7):1704-1717, 2009. URL: http://dx.doi.org/10.1016/j.ejc.2009.03.002.
  19. Gerhard Ringel. Das Geschlecht des vollständigen paaren Graphen. Abh. Math. Sem. Univ. Hamburg, 28:139-150, 1965. URL: http://dx.doi.org/10.1007/BF02993245.
  20. Neil Robertson and Richard Vitray. Representativity of surface embeddings. In Paths, flows, and VLSI-layout (Bonn, 1988), volume 9 of Algorithms Combin., pages 293-328. Springer, Berlin, 1990. Google Scholar
  21. Marcus Schaefer. Hanani-Tutte and related results. In Geometry - intuitive, discrete, and convex, volume 24 of Bolyai Soc. Math. Stud., pages 259-299. János Bolyai Math. Soc., Budapest, 2013. URL: http://dx.doi.org/10.1007/978-3-642-41498-5_10.
  22. Marcus Schaefer and Daniel Štefankovič. Block additivity of ℤ₂-embeddings. In Graph drawing, volume 8242 of Lecture Notes in Comput. Sci., pages 185-195. Springer, Cham, 2013. URL: http://dx.doi.org/10.1007/978-3-319-03841-4_17.
  23. Paul Seymour, 2017. Personal communication. Google Scholar
  24. W. T. Tutte. Toward a theory of crossing numbers. J. Combinatorial Theory, 8:45-53, 1970. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact