Document Open Access Logo

Strong Hanani-Tutte for the Torus

Authors Radoslav Fulek , Michael J. Pelsmajer, Marcus Schaefer

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.38.pdf
  • Filesize: 0.85 MB
  • 15 pages

Document Identifiers

Author Details

Radoslav Fulek
  • Department of Mathematics, UC San Diego, La Jolla, CA, USA
Michael J. Pelsmajer
  • Department of Applied Mathematics, Illinois Institute of Technology, Chicago, IL, USA
Marcus Schaefer
  • Department of Computer Science, DePaul University, Chicago, IL, USA

Funding

  • Schaefer, Marcus: This work was supported by a DePaul/CDM Faculty Summer Research Stipend Program.

Cite AsGet BibTex

Radoslav Fulek, Michael J. Pelsmajer, and Marcus Schaefer. Strong Hanani-Tutte for the Torus. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.38

Abstract

If a graph can be drawn on the torus so that every two independent edges cross an even number of times, then the graph can be embedded on the torus.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graphs and surfaces
Keywords
  • Graph Embedding
  • Torus
  • Hanani-Tutte Theorem
  • Intersection Form

Metrics

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

Related Versions

References

  1. Grant Cairns and Yury Nikolayevsky. Bounds for generalized thrackles. Discrete Comput. Geom., 23(2):191-206, 2000. Google Scholar
  2. Chaim Chojnacki (Haim Hanani). Über wesentlich unplättbare Kurven im drei-dimensionalen Raume. Fundamenta Mathematicae, 23:135-142, 1934. Google Scholar
  3. David Cimasoni and Nicolai Reshetikhin. Dimers on surface graphs and spin structures. i. Communications in Mathematical Physics, 275(1):187-208, 2007. Google Scholar
  4. É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. Journal of Graph Algorithms and Applications, 21(5):939-981, 2017. URL: https://doi.org/10.7155/jgaa.00445.
  5. Hooman R. Dehkordi and Graham Farr. Non-separating planar graphs. Electron. J. Comb., 28(1):P1.43, 16, 2021. Google Scholar
  6. Reinhard Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, third edition, 2005. Google Scholar
  7. Radoslav Fulek and Jan Kynčl. Hanani-Tutte for approximating maps of graphs. In 34th International Symposium on Computational Geometry, SoCG 2018, June 11-14, 2018, Budapest, Hungary, pages 39:1-39:15, 2018. (full version: https://arxiv.org/pdf/1705.05243.pdf). URL: https://doi.org/10.4230/LIPIcs.SoCG.2018.39.
  8. Radoslav Fulek and Jan Kynčl. Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4. Combinatorica, 39(6):1267-1279, 2019. Google Scholar
  9. Radoslav Fulek and Jan Kynčl. ℤ₂-Genus of Graphs and Minimum Rank of Partial Symmetric Matrices. In 35th International Symposium on Computational Geometry (SoCG 2019), Leibniz International Proceedings in Informatics (LIPIcs), pages 39:1-39:16, 2019. Google Scholar
  10. Radoslav Fulek, Jan Kynčl, and Dömötör Pálvölgyi. Unified Hanani-Tutte theorem. Electr. J. Comb., 24(3):P3.18, 2017. Google Scholar
  11. Radoslav Fulek and Jan Kynčl. The ℤ₂-genus of Kuratowski minors. In 34th International Symposium on Computational Geometry, SoCG 2018, June 11-14, 2018, Budapest, Hungary, pages 40:1-40:14, 2018. URL: https://doi.org/10.4230/LIPIcs.SoCG.2018.40.
  12. Radoslav Fulek, Michael Pelsmajer, Marcus Schaefer, and Daniel Štefankovič. Hanani-Tutte, monotone drawings, and level-planarity. In János Pach, editor, Thirty Essays on Geometric Graph Theory, pages 263-287. Springer, 2013. Google Scholar
  13. Radoslav Fulek, Michael J. Pelsmajer, and Marcus Schaefer. Hanani-Tutte for radial planarity II. In Yifan Hu and Martin Nöllenburg, editors, Graph Drawing and Network Visualization - 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers, volume 9801 of Lecture Notes in Computer Science, pages 468-481. Springer, 2016. Google Scholar
  14. Radoslav Fulek, Michael J. Pelsmajer, and Marcus Schaefer. Hanani-Tutte for radial planarity. J. Graph Algorithms Appl., 21(1):135-154, 2017. Google Scholar
  15. Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer, and Daniel Štefankovič. Adjacent crossings do matter. Journal of Graph Algorithms and Applications, 16(3):759-782, 2012. Google Scholar
  16. Carsten Gutwenger, Petra Mutzel, and Marcus Schaefer. Practical experience with Hanani-Tutte for testing c-planarity. In Catherine C. McGeoch and Ulrich Meyer, editors, 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 86-97. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973198.9.
  17. Balázs Keszegh. Coloring intersection hypergraphs of pseudo-disks. Discrete & Computational Geometry, pages 1-23, 2019. Google Scholar
  18. Jan Kynčl. Reply to "issue update: in graph theory, different definitions of edge crossing numbers - impact on applications?". https://mathoverflow.net/questions/366765/issue-update-in-graph-theory-different-definitions-of-edge-crossing-numbers (last accessed 8/6/2020), 2020.
  19. Martin Loebl and Gregor Masbaum. On the optimality of the Arf invariant formula for graph polynomials. Adv. Math., 226(1):332-349, 2011. Google Scholar
  20. Bojan Mohar. The genus crossing number. Ars Math. Contemp., 2(2):157-162, 2009. Google Scholar
  21. Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 2001. Google Scholar
  22. Serguei Norine. Pfaffian graphs, t-joins and crossing numbers. Combinatorica, 28(1):89-98, 2008. Google Scholar
  23. János Pach and Micha Sharir. On the boundary of the union of planar convex sets. Discrete Comput. Geom., 21(3):321-328, 1999. Google Scholar
  24. János Pach and Géza Tóth. Thirteen problems on crossing numbers. Geombinatorics, 9(4):194-207, 2000. Google Scholar
  25. Michael J. Pelsmajer, Marcus Schaefer, and Despina Stasi. Strong Hanani-Tutte on the projective plane. SIAM J. Discrete Math., 23(3):1317-1323, 2009. Google Scholar
  26. Michael J. Pelsmajer, Marcus Schaefer, and Daniel Štefankovič. Removing even crossings. J. Combin. Theory Ser. B, 97(4):489-500, 2007. Google Scholar
  27. Michael J. Pelsmajer, Marcus Schaefer, and Daniel Štefankovič. Odd crossing number and crossing number are not the same. Discrete Comput. Geom., 39(1):442-454, 2008. Google Scholar
  28. Michael J. Pelsmajer, Marcus Schaefer, and Daniel Štefankovič. Removing even crossings on surfaces. European J. Combin., 30(7):1704-1717, 2009. Google Scholar
  29. Michael J. Pelsmajer, Marcus Schaefer, and Daniel Štefankovič. Removing independently even crossings. SIAM Journal on Discrete Mathematics, 24(2):379-393, 2010. Google Scholar
  30. Marcus Schaefer. The graph crossing number and its variants: A survey. The Electronic Journal of Combinatorics, 20:1-90, 2013. Dynamic Survey, #DS21, last updated September 2020. Google Scholar
  31. Marcus Schaefer. Toward a theory of planarity: Hanani-Tutte and planarity variants. Journal of Graph Algortihms and Applications, 17(4):367-440, 2013. Google Scholar
  32. Marcus Schaefer. Hanani-Tutte and related results. In I. Bárány, K. J. Böröczky, G. Fejes Tóth, and J. Pach, editors, Geometry - Intuitive, Discrete, and Convex - A Tribute to László Fejes Tóth, volume 24 of Bolyai Society Mathematical Studies. Springer, Berlin, 2014. Google Scholar
  33. Shakhar Smorodinsky and Micha Sharir. Selecting points that are heavily covered by pseudo-circles, spheres or rectangles. Combin. Probab. Comput., 13(3):389-411, 2004. Google Scholar
  34. Glenn Tesler. Matchings in graphs on non-orientable surfaces. Journal of Combinatorial Theory, Series B, 78(2):198-231, 2000. Google Scholar
  35. William T. Tutte. Toward a theory of crossing numbers. J. Combinatorial Theory, 8:45-53, 1970. Google Scholar
  36. S. Whitesides and R. Zhao. K-admissible collections of Jordan curves and offsets of circular arc figures. Technical Report SOCS 90.08, McGill University, 1990. 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 Imprint Privacy Contact