Taking a detour; or, Gioan’s theorem, and pseudolinear drawings of complete graphs. (English) Zbl 1467.05178
Summary: We describe a uniform approach to two known graph drawing results including E. Gioan’s theorem [Lect. Notes Comput. Sci. 3787, 139–150 (2005; Zbl 1171.05323)], stating that any two good drawings of a complete graph with the same rotation system are isomorphic up to Reidemeister moves of type 3, and a characterization of pseudolinear drawings of the complete graph via an excluded configuration: a bad \(K_4\). Our approach yields a new and short self-contained proof of Gioan’s theorem [loc. cit.], and a short proof of the pseudolinearity characterization using a previous result. As a bonus we obtain an extension of Gioan’s theoremE. Gioan to the family of graphs \(K_n-M\), where \(M\) is a non-perfect matching in \(K_n\), \(n \ge 5\).
MSC:
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 52C30 | Planar arrangements of lines and pseudolines (aspects of discrete geometry) |
Citations:
Zbl 1171.05323References:
| [1] | 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), booklet of abstracts, pp. 33-36. http://dccg.upc.edu/egc15/en/program/ |
| [2] | Arroyo, A.; McQuillan, D.; Richter, RB; Salazar, G., Levi’s lemma, pseudolinear drawings of \(K_n\), and empty triangles, J. Graph Theory, 87, 4, 443-459 (2018) · Zbl 1388.52018 · doi:10.1002/jgt.22167 |
| [3] | Balko, M., Fulek, R., Kynčl, J.: Crossing numbers and combinatorial characterization of monotone drawings of \(K_n (2013)\).arXiv:1312.3679 · Zbl 1307.05058 |
| [4] | 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) · Zbl 1307.05058 · doi:10.1007/s00454-014-9644-z |
| [5] | Cairns, G.; Groves, E.; Nikolayevsky, Y., Bad drawings of small complete graphs, Australas. J. Combin., 75, 322-342 (2019) · Zbl 1429.05147 |
| [6] | Eggleton, R.B.: Crossing Numbers of Graphs. PhD thesis, University of Calgary (1973) |
| [7] | Gioan, E.: Complete graph drawings up to triangle mutations. In: Graph-Theoretic Concepts in Computer Science (Metz 2005). Lecture Notes in Computer Science, vol. 3787, pp. 139-150. Springer, Berlin (2005) · Zbl 1171.05323 |
| [8] | Goodman, JE, Proof of a conjecture of Burr, Grünbaum, and Sloane, Discrete Math., 32, 1, 27-35 (1980) · Zbl 0444.05029 · doi:10.1016/0012-365X(80)90096-5 |
| [9] | Gronau, H.-D.O.F., Harborth, H.: Numbers of nonisomorphic drawings for small graphs. In: 20th Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton 1989). Congress Numerical, vol. 71, pp. 105-114. Charles Babbage Research Centre, Winnipeg (1990) · Zbl 0696.05022 |
| [10] | Hass, J.; Scott, P., Intersections of curves on surfaces, Israel J. Math., 51, 1-2, 90-120 (1985) · Zbl 0576.57009 · doi:10.1007/BF02772960 |
| [11] | Kynčl, J., Enumeration of simple complete topological graphs, Eur. J. Comb., 30, 7, 1676-1685 (2009) · Zbl 1228.05175 · doi:10.1016/j.ejc.2009.03.005 |
| [12] | Kynčl, J., Simple realizability of complete abstract topological graphs in P, Discrete Comput. Geom., 45, 3, 383-399 (2011) · Zbl 1214.05013 · doi:10.1007/s00454-010-9320-x |
| [13] | Mohar, B.; Thomassen, C., Graphs on Surfaces (2001), Baltimore: Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore · Zbl 0979.05002 |
| [14] | Pach, J.; Solymosi, J.; Tóth, G., Unavoidable configurations in complete topological graphs, Discrete Comput. Geom., 30, 2, 311-320 (2003) · Zbl 1042.05030 · doi:10.1007/s00454-003-0012-9 |
| [15] | Pach, J.; Tóth, G., How many ways can one draw a graph?, Combinatorica, 26, 5, 559-576 (2006) · Zbl 1121.05006 · doi:10.1007/s00493-006-0032-z |
| [16] | Schaefer, M., Crossing Numbers of Graphs. Discrete Mathematics and its Applications. (2018), Boca Raton: CRC Press, Boca Raton · Zbl 1388.05005 · doi:10.1201/9781315152394 |
| [17] | Schaefer, M.: A proof of Levi’s extension lemma (2019).arXiv:1910.05388 |
| [18] | Tutte, WT, How to draw a graph, Proc. Lond. Math. Soc., 13, 743-767 (1963) · Zbl 0115.40805 · doi:10.1112/plms/s3-13.1.743 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
