Document Open Access Logo

Drawings of Complete Multipartite Graphs up to Triangle Flips

Authors Oswin Aichholzer , Man-Kwun Chiu , Hung P. Hoang , Michael Hoffmann , Jan Kynčl , Yannic Maus , Birgit Vogtenhuber , Alexandra Weinberger

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2023.6.pdf
  • Filesize: 1.54 MB
  • 16 pages

Document Identifiers

Author Details

Oswin Aichholzer
  • Technische Universität Graz, Austria
Man-Kwun Chiu
  • Wenzhou-Kean University, Wenzhou, China
Hung P. Hoang
  • Department of Computer Science, ETH Zürich, Switzerland
Michael Hoffmann
  • Department of Computer Science, ETH Zürich, Switzerland
Jan Kynčl
  • Charles University, Prague, Czech Republic
Yannic Maus
  • Technische Universität Graz, Austria
Birgit Vogtenhuber
  • Technische Universität Graz, Austria
Alexandra Weinberger
  • Technische Universität Graz, Austria

Funding

  • Aichholzer, Oswin: partially supported by the Austrian Science Fund (FWF): W1230.
  • Chiu, Man-Kwun: partially supported by ERC StG 757609. Part of the work was done while Chiu was at FU Berlin.
  • Hoffmann, Michael: supported by the Swiss National Science Foundation within the collaborative D-A-CH project Arrangements and Drawings as SNSF project 200021E-171681.
  • Kynčl, Jan: supported by the grant no. 22-19073S of the Czech Science Foundation (GAČR).
  • Vogtenhuber, Birgit: partially supported by the Austrian Science Fund within the collaborative D-A-CH project Arrangements and Drawings as FWF project I 3340-N35.
  • Weinberger, Alexandra: supported by the Austrian Science Fund (FWF): W1230.

Cite AsGet BibTex

Oswin Aichholzer, Man-Kwun Chiu, Hung P. Hoang, Michael Hoffmann, Jan Kynčl, Yannic Maus, Birgit Vogtenhuber, and Alexandra Weinberger. Drawings of Complete Multipartite Graphs up to Triangle Flips. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.SoCG.2023.6

Abstract

For a drawing of a labeled graph, the rotation of a vertex or crossing is the cyclic order of its incident edges, represented by the labels of their other endpoints. The extended rotation system (ERS) of the drawing is the collection of the rotations of all vertices and crossings. A drawing is simple if each pair of edges has at most one common point. Gioan’s Theorem states that for any two simple drawings of the complete graph K_n with the same crossing edge pairs, one drawing can be transformed into the other by a sequence of triangle flips (a.k.a. Reidemeister moves of Type 3). This operation refers to the act of moving one edge of a triangular cell formed by three pairwise crossing edges over the opposite crossing of the cell, via a local transformation. We investigate to what extent Gioan-type theorems can be obtained for wider classes of graphs. A necessary (but in general not sufficient) condition for two drawings of a graph to be transformable into each other by a sequence of triangle flips is that they have the same ERS. As our main result, we show that for the large class of complete multipartite graphs, this necessary condition is in fact also sufficient. We present two different proofs of this result, one of which is shorter, while the other one yields a polynomial time algorithm for which the number of needed triangle flips for graphs on n vertices is bounded by O(n^{16}). The latter proof uses a Carathéodory-type theorem for simple drawings of complete multipartite graphs, which we believe to be of independent interest. Moreover, we show that our Gioan-type theorem for complete multipartite graphs is essentially tight in the following sense: For the complete bipartite graph K_{m,n} minus two edges and K_{m,n} plus one edge for any m,n ≥ 4, as well as K_n minus a 4-cycle for any n ≥ 5, there exist two simple drawings with the same ERS that cannot be transformed into each other using triangle flips. So having the same ERS does not remain sufficient when removing or adding very few edges.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorics
  • Mathematics of computing → Graph theory
  • Human-centered computing → Graph drawings
Keywords
  • Simple drawings
  • simple topological graphs
  • complete graphs
  • multipartite graphs
  • k-partite graphs
  • bipartite graphs
  • Gioan’s Theorem
  • triangle flips
  • Reidemeister moves

Metrics

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

Related Versions

References

  1. Bernado M. Ábrego, Oswin Aichholzer, Silvia Fernández-Merchant, Thomas Hackl, Jürgen Pammer, Alexander Pilz, Pedro Ramos, Gelasio Salazar, and Birgit Vogtenhuber. All Good Drawings of Small Complete Graphs. In Proc. 31^st European Workshop on Computational Geometry EuroCG '15, pages 57-60, Ljubljana, Slovenia, 2015. URL: http://www.csun.edu/~sf70713/publications/all_good_drawings_2015.pdf.
  2. Oswin Aichholzer, Alfredo García, Irene Parada, Birgit Vogtenhuber, and Alexandra Weinberger. Shooting stars in simple drawings of K_m,n. In Patrizio Angelini and Reinhard von Hanxleden, editors, Graph Drawing and Network Visualization, pages 49-57, Cham, 2023. Springer International Publishing. URL: https://doi.org/10.1007/978-3-031-22203-0_5.
  3. James W. Alexander and Garland B. Briggs. On types of knotted curves. Ann. Math., 28(1/4):562-586, 1927. URL: https://doi.org/10.2307/1968399.
  4. Alan Arroyo, Dan McQuillan, R. Bruce Richter, and Gelasio Salazar. Drawings of K_n with the same rotation scheme are the same up to triangle-flips (Gioan’s theorem). Australas. J. Comb., 67(2):131-144, 2017. URL: https://ajc.maths.uq.edu.au/pdf/67/ajc_v67_p131.pdf.
  5. Alan Arroyo, Dan McQuillan, R. Bruce Richter, and Gelasio Salazar. Levi’s lemma, pseudolinear drawings of K_n, and empty triangles. J. Graph Theory, 87(4):443-459, 2018. URL: https://doi.org/10.1002/jgt.22167.
  6. Martin Balko, Radoslav Fulek, and Jan Kynčl. Crossing numbers and combinatorial characterization of monotone drawings of K_n. Discrete Comput. Geom., 53:107-143, 2015. URL: https://doi.org/10.1007/s00454-014-9644-z.
  7. Helena Bergold, Stefan Felsner, Manfred Scheucher, Felix Schröder, and Raphael Steiner. Topological drawings meet classical theorems from convex geometry. In Proc. 28th Internat. Sympos. Graph Drawing, volume 12590 of Lecture Notes Comput. Sci., pages 281-294. Springer-Verlag, 2020. URL: https://doi.org/10.1007/978-3-030-68766-3_22.
  8. Jean Cardinal and Stefan Felsner. Topological drawings of complete bipartite graphs. J. Comput. Geom, 9(1):213-246, 2018. URL: https://doi.org/10.20382/jocg.v9i1a7.
  9. Hsien-Chih Chang, Jeff Erickson, David Letscher, Arnaud de Mesmay, Saul Schleimer, Eric Sedgwick, Dylan Thurston, and Stephan Tillmann. Tightening curves on surfaces via local moves. In Proc. 29th ACM-SIAM Sympos. Discrete Algorithms, pages 121-135, 2018. URL: https://doi.org/10.1137/1.9781611975031.8.
  10. Julia Chuzhoy and Zihan Tan. A subpolynomial approximation algorithm for graph crossing number in low-degree graphs. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pages 303-316, New York, NY, USA, 2022. Association for Computing Machinery. URL: https://doi.org/10.1145/3519935.3519984.
  11. Walter Didimo, Giuseppe Liotta, and Fabrizio Montecchiani. A survey on graph drawing beyond planarity. ACM Comput. Surv., 52(1):4:1-4:37, 2019. URL: https://doi.org/10.1145/3301281.
  12. Paul Erdős and Richard K. Guy. Crossing number problems. Am. Math. Mon., 88:52-58, 1973. URL: https://doi.org/10.2307/2319261.
  13. Benson Farb and Dan Margalit. A primer on mapping class groups, volume 49 of Princeton Mathematical Series. Princeton University Press, Princeton, NJ, 2012. Google Scholar
  14. Stefan Felsner, Alexander Pilz, and Patrick Schnider. Arrangements of approaching pseudo-lines. Discrete Comput. Geom., 67:380-402, March 2022. URL: https://doi.org/10.1007/s00454-021-00361-w.
  15. Emeric Gioan. Complete graph drawings up to triangle mutations. In Proc. 31st Internat. Workshop Graph-Theoret. Concepts Comput. Sci., volume 3787 of Lecture Notes Comput. Sci., pages 139-150. Springer, 2005. URL: https://doi.org/10.1007/11604686_13.
  16. Emeric Gioan. Complete graph drawings up to triangle mutations. Discrete Comput. Geom., 67:985-1022, 2022. URL: https://doi.org/10.1007/s00454-021-00339-8.
  17. Jonathan L. Gross and Thomas W. Tucker. Topological graph theory. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons Inc., New York, 1987. A Wiley-Interscience Publication. Google Scholar
  18. Heiko Harborth. Empty triangles in drawings of the complete graph. Discrete Math., 191:109-111, 1998. URL: https://doi.org/10.1016/S0012-365X(98)00098-3.
  19. Joel Hass and Peter Scott. Intersections of curves on surfaces. Isr. J. Math., 51(1-2):90-120, 1985. Google Scholar
  20. Noboru Ito and Yusuke Takimura. (1,2) and weak (1,3) homotopies on knot projections. J. Knot Theory Ramif., 22(14), 2013. URL: https://doi.org/10.1142/S0218216513500855.
  21. Louis H. Kauffman. Invariants of graphs in three-space. Trans. Am. Math. Soc., 311(2):697-710, 1989. URL: https://doi.org/10.1090/S0002-9947-1989-0946218-0.
  22. Jan Kynčl. Enumeration of simple complete topological graphs. Eur. J. Comb., 30:1676-1685, 2009. URL: https://doi.org/10.1016/j.ejc.2009.03.005.
  23. Jan Kynčl. Simple realizability of complete abstract topological graphs in P. Discrete Comput. Geom., 45:383-399, 2011. URL: https://doi.org/10.1007/s00454-010-9320-x.
  24. Jan Kynčl. Improved enumeration of simple topological graphs. Discrete Comput. Geom., 50:727-770, 2013. URL: https://doi.org/10.1007/s00454-013-9535-8.
  25. Marc Lackenby. A polynomial upper bound on Reidemeister moves. Ann. Math., 82(2):491-564, 2015. URL: https://doi.org/10.4007/annals.2015.182.2.3.
  26. János Pach, József Solymosi, and Géza Tóth. Unavoidable configurations in complete topological graphs. Discrete Comput. Geom., 30(2):311-320, 2003. URL: https://doi.org/10.1007/s00454-003-0012-9.
  27. János Pach and Géza Tóth. How many ways can one draw a graph? Combinatorica, 26(5):559-576, 2006. URL: https://doi.org/10.1007/s00493-006-0032-z.
  28. Kurt Reidemeister. Elementare Begründung der Knotentheorie. Abh. Math. Sem. Univ. Hamburg, 5:24-32, 1927. URL: https://doi.org/10.1007/BF02952507.
  29. Gerhard Ringel. Teilungen der Ebene durch Geraden oder topologische Geraden. Math. Z., 64:79-102, 1956. URL: https://doi.org/10.1007/BF01166556.
  30. Jean-Pierre Roudneff. Tverberg-type theorems for pseudoconfigurations of points in the plane. Eur. J. Comb., 9(2):189-198, 1988. URL: https://doi.org/10.1016/S0195-6698(88)80046-5.
  31. Marcus Schaefer. Taking a detour; or, Gioan’s theorem, and pseudolinear drawings of complete graphs. Discrete Comput. Geom., 66:12-31, 2021. URL: https://doi.org/10.1007/s00454-021-00296-2.
  32. Jack Snoeyink and John Hershberger. Sweeping arrangements of curves. In Discrete and Computational Geometry: Papers from the DIMACS Special Year, volume 6 of DIMACS, pages 309-349. AMS, 1991. URL: https://doi.org/10.1090/dimacs/006/21.
  33. László A. Székely. A successful concept for measuring non-planarity of graphs: the crossing number. Discr. Math., 276(1):331-352, 2004. 6th International Conference on Graph Theory. URL: https://doi.org/10.1016/S0012-365X(03)00317-0.
  34. Csaba D. Tóth, Joseph O'Rourke, and Jacob E. Goodman, editors. Handbook of Discrete and Computational Geometry, Third Edition. Chapman and Hall/CRC, 2017. URL: https://www.routledge.com/9781498711395.
  35. Bruce Trace. On the Reidemeister moves of a classical knot. Proc. Amer. Math. Soc., 89(4):722-724, 1983. URL: https://doi.org/10.1090/S0002-9939-1983-0719004-4.
  36. Shûji Yamada. An invariant of spatial graphs. J. Graph Theory, 13(5):537-551, 1989. URL: https://doi.org/10.1002/jgt.3190130503.
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