Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

Complete Graph Drawings up to Triangle Mutations

  • Published:
Discrete & Computational Geometry Aims and scope Submit manuscript

Abstract

The main result of the paper can be stated in the following way: a complete graph drawing in the sphere, where two edges have at most one common point, which is either a crossing or a common endpoint, and no three edges share a crossing, is determined by the circular ordering of edges at each vertex, or equivalently by the set of pairs of edges that cross, up to homeomorphism and a sequence of triangle mutations. A triangle mutation (or switch, or flip) consists in passing an edge across the intersection of two other edges, assuming the three edges cross each other and the region delimited by the three edges has an empty intersection with the drawing. Equivalently, the result holds for a drawing in the plane assuming the drawing is given with a pair of edges indicating where the unbounded region is. The proof is constructive, based on an inductive algorithm that adds vertices and their incident edges one by one (actually yielding an extra property for the sequence of triangle mutations). This result generalizes Ringel’s theorem on uniform pseudoline arrangements (or rank 3 uniform oriented matroids) to complete graph drawings. We also apply this result to plane projections (or visualizations) of a geometric spatial complete graph, in terms of the rank 4 uniform oriented matroid defined by its vertices. Independently, we prove that, for a complete graph drawing, the set of pairs of edges that cross determine, by first order logic formulas, the circular ordering of edges at each vertex, as well as further information.

This is a preview of subscription content,log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21
Fig. 22
Fig. 23
Fig. 24

Similar content being viewed by others

References

  1. Ábrego, B., Aichholzer, O., Fernández-Merchant, S., Hackl, T., Pammer, J., Pilz, A., Ramos, P., Sala-zar, G., Vogtenhuber, B.: All good drawings of small complete graphs. In: 31th European Workshop on Computational Geometry (Ljubljana 2015). Book of Abstracts, pp. 57–60.http://eurocg15.fri.uni-lj.si/pub/eurocg15-book-of-abstracts.pdf

  2. Aichholzer, O., Balko, M., Hoffmann, M., Kynčl, J., Mulzer, W., Parada, I., Pilz, A., Scheucher, M., Valtr, P., Vogtenhuber, B., Welzl, E.: Minimal representations of order types by geometric graphs. In: Graph Drawing and Network Visualization (Prague 2019). Lecture Notes in Computer Science, vol. 11904, pp. 101–113. Springer, Cham (2019). Full version:arXiv:1908.05124

  3. Aichholzer, O., Hackl, T., Pilz, A., Ramos, P., Sacristán, V., Vogtenhuber, B.: Empty triangles in good drawings of the complete graph. In: Mexican Conference on Discrete Mathematics and Computational Geometry (Oaxaca 2013), pp. 21–29 (2013)

  4. Aichholzer, O., Hackl, T., Pilz, A., Salazar, G., Vogtenhuber, B.: Deciding monotonicity of good drawings of the complete graph. In: 16th Spanish Meeting on Computational Geometry (Barcelona 2015), pp. 33–36 (2015)

  5. Arroyo, A., McQuillan, D., Richter, R.B., Salazar, G.: Drawings of\(K_n\) with the same rotation scheme are the same up to triangle-flips (Gioan’s theorem). Australas. J. Combin.67, 131–144 (2017)

    MathSciNet MATH  Google Scholar 

  6. Arroyo, A., McQuillan, D., Richter, R.B., Salazar, G.: Convex drawings of the complete graph: topology meets geometry (2017).arXiv:1712.06380

  7. Arroyo, A., McQuillan, D., Richter, R.B., Salazar, G.: Levi’s lemma, pseudolinear drawings of\(K_n\), and empty triangles. J. Graph Theory87(4), 443–459 (2018)

    Article MathSciNet  Google Scholar 

  8. Balko, M., Fulek, R., Kynčl, J.: Crossing numbers and combinatorial characterization of monotone drawings of\(K_n\). Discrete Comput. Geom.53(1), 107–143 (2015)

    Article MathSciNet  Google Scholar 

  9. Bergold, H., Felsner, S., Scheucher, M., Schröder, F., Steiner, R.: Topological drawings meet classical theorems from convex geometry. In: 36th European Workshop on Computational Geometry (Würzburg 2020). Book of Abstracts, # 12.https://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/eurocg20-proceedings.pdf

  10. Björner, A., Las Vergnas, M., Sturmfels, B., White, N., Ziegler, G.M.: Oriented Matroids. Encyclopedia of Mathematics and its Applications, vol. 46. Cambridge University Press, Cambridge (1999)

    MATH  Google Scholar 

  11. Bokowski, J., Pisanski, T.: Oriented matroids and complete-graph embeddings on surfaces. J. Comb. Theory Ser. A114(1), 1–19 (2007)

    Article MathSciNet  Google Scholar 

  12. Courcelle, B.: The monadic second-order logic of graphs. XIII. Graph drawings with edge crossings. Theoret. Comput. Sci.244(1–2), 63–94 (2000)

    Article MathSciNet  Google Scholar 

  13. Courcelle, B., Olive, F.: Une axiomatisation au premier ordre des arrangements de pseudodroites euclidiennes. Ann. Inst. Fourier (Grenoble)49(3), 883–903 (1999)

    Article MathSciNet  Google Scholar 

  14. Felsner, S., Weil, H.: A theorem on higher Bruhat orders. Discrete Comput. Geom.23(1), 121–127 (2000)

    Article MathSciNet  Google Scholar 

  15. Gioan, E.: Complete graph drawings up to triangle mutations. In: Graph-Theoretic Concepts in Computer Science (Metz 2005). Lecture Notes in Comput. Sci., vol. 3787, pp. 139–150. Springer, Berlin (2005). (preliminary conference version of the present paper)

  16. Harborth, H.: Empty triangles in drawings of the complete graph. Discrete Math.191(1–3), 109–111 (1998)

    Article MathSciNet  Google Scholar 

  17. Kratochvíl, J., Lubiw, A., Nešetřil, J.: Noncrossing subgraphs in topological layouts. SIAM J. Discrete Math.4(2), 223–244 (1991)

    Article MathSciNet  Google Scholar 

  18. Kynčl, J.: Enumeration of simple complete topological graphs. Eur. J. Comb.30(7), 1676–1685 (2009)

    Article MathSciNet  Google Scholar 

  19. Kynčl, J.: Simple realizability of complete abstract topological graphs in P. Discrete Comput. Geom.45(3), 383–399 (2011)

    Article MathSciNet  Google Scholar 

  20. Kynčl, J.: Improved enumeration of simple topological graphs. Discrete Comput. Geom.50(3), 727–770 (2013)

    Article MathSciNet  Google Scholar 

  21. Mnëv, N.E.: The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In: Topology and Geometry–Rohlin Seminar. Lecture Notes in Math., vol. 1346, pp. 527–543. Springer, Berlin (1988)

  22. Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (2001)

  23. Oh, S.: Chambers of wiring diagrams. Discrete Math.339(10), 2511–2514 (2016)

    Article MathSciNet  Google Scholar 

  24. Pach, J., Tóth, G.: How many ways can one draw a graph? Combinatorica26(5), 559–576 (2006)

    Article MathSciNet  Google Scholar 

  25. Ringel, G.: Über Geraden in allgemeiner Lage. Elem. Math.12, 75–82 (1957)

    MathSciNet MATH  Google Scholar 

  26. Roudneff, J.-P.: Tverberg-type theorems for pseudoconfigurations of points in the plane. Eur. J. Comb.9(2), 189–198 (1988)

    Article MathSciNet  Google Scholar 

  27. Schaefer, M.: Crossing Numbers of Graphs. Discrete Mathematics and Its Applications. CRC Press, Boca Raton (2018)

    Book  Google Scholar 

  28. Schaefer, M.: Taking a detour; or, Gioan’s theorem, and pseudolinear drawings of complete graphs. Discrete Comput. Geom.66(1), 12–31 (2021)

    Article MathSciNet  Google Scholar 

Download references

Acknowledgements

I am very grateful to three reviewers for their meticulous reading and numerous useful comments. I wish to thank Jean Cardinal for a discussion yielding to the bipartite counter-example of Fig. 3. I am also grateful to the authors of [5] for informing me of their initiative to complete the proof of the main result announced in [15] and for inviting me to complete it in parallel; and I am grateful in particular to Bruce Richter for friendly discussions and useful comments when sharing our respective preprints (the final gap between publication dates is due to some delay in the revision of the present paper).

Author information

Authors and Affiliations

  1. LIRMM, Université de Montpellier, CNRS, Montpellier, France

    Emeric Gioan

Authors
  1. Emeric Gioan

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toEmeric Gioan.

Additional information

Editor in Charge: János Pach

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This research was part of the OMSMO Project (Oriented Matroids for Shape Modeling), supported by the Grant “Chercheur d’avenir 2015” (Région Occitanie, and Fonds Européen de Développement Régional FEDER)

Rights and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gioan, E. Complete Graph Drawings up to Triangle Mutations.Discrete Comput Geom67, 985–1022 (2022). https://doi.org/10.1007/s00454-021-00339-8

Download citation

Keywords

Mathematics Subject Classification

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp