×

Extending drawings of complete graphs into arrangements of pseudocircles. (English) Zbl 1465.05117

Summary: Motivated by the successful application of geometry to proving the Harary-Hill conjecture for “pseudolinear” drawings of \(K_n\), we introduce “pseudospherical” drawings of graphs. A spherical drawing of a graph \(G\) is a drawing in the unit sphere \(\mathbb{S}^2\) in which the vertices of \(G\) are represented as points – no three on a great circle – and the edges of \(G\) are shortest-arcs in \(\mathbb{S}^2\) connecting pairs of vertices. Such a drawing has three properties: (1) every edge \(e\) is contained in a simple closed curve \(\gamma_e\) such that the only vertices in \(\gamma_e\) are the ends of \(e\); (2) if \(e\ne f\), then \(\gamma_e\cap\gamma_f\) has precisely two crossings; and (3) if \(e\ne f\), then \(e\) intersects \(\gamma_f\) at most once, in either a crossing or an end of \(e\). We use properties (1)–(3) to define a pseudospherical drawing of \(G\). Our main result is that for the complete graph, properties (1)–(3) are equivalent to the same three properties but with “precisely two crossings” in (2) replaced by “at most two crossings.” The proof requires a result in the geometric transversal theory of arrangements of pseudocircles. This is proved using the surprising result that the absence of special arcs (coherent spirals) in an arrangement of simple closed curves characterizes the fact that any two curves in the arrangement have at most two crossings. Our studies provide the necessary ideas for exhibiting a drawing of \(K_{10}\) that has no extension to an arrangement of pseudocircles and a drawing of \(K_9\) that does extend to an arrangement of pseudocircles, but no such extension has all pairs of pseudocircles crossing twice.

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
52C10 Erdős problems and related topics of discrete geometry
52C30 Planar arrangements of lines and pseudolines (aspects of discrete geometry)

Software:

MathOverflow
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] B. M. Ábrego and S. Fernández-Merchant, A lower bound for the rectilinear crossing number, Graphs Combin., 21 (2005), pp. 293-300. · Zbl 1075.05022
[2] B. M. Ábrego, O. Aichholzer, S. Fernández-Merchant, T. Hackl, J. Pammer, A. Pilz, P. Ramos, G. Salazar, and B. Vogtenhuber, All good drawings of small complete graphs, in Proc. 31st European Workshop on Computational Geometry (EuroCG ’15), Ljubljana, Slovenia, 2015, pp. 57-60.
[3] B. M. Ábrego, O. Aichholzer, S. Fernández-Merchant, D. McQuillan, B. Mohar, P. Mutzel, P. Ramos, R. B. Richter, and B. Vogtenhuber, Bishellable drawings of \(K_n\), SIAM J. Discrete Math., 32 (2018), pp. 2482-2492, https://doi.org/10.1137/17M1147974. · Zbl 1400.05061
[4] B. M. Ábrego, O. Aichholzer, S. Fernández-Merchant, P. Ramos, and G. Salazar, Shellable drawings and the cylindrical crossing number of \(K_n\), Discrete Comput. Geom., 52 (2014), pp. 743-753. · Zbl 1306.05166
[5] B. M. Ábrego, O. Aichholzer, S. Fernández-Merchant, P. Ramos, and B. Vogtenhuber, Non-shellable drawings of \(K_n\) with few crossings, in Proc. 26th Annual Canadian Conference on Computational Geometry (CCCG), Halifax, Nova Scotia, 2014, pp. 46-51.
[6] B. M. Ábrego, O. Aichholzer, S. Fernández-Merchant, P. Ramos, and G. Salazar, The \(2\)-page crossing number of \(K_n\), Discrete Comput. Geom., 49 (2013), pp. 747-777. · Zbl 1269.05078
[7] O. Aichholzer, J. García, D. Orden, and P. Ramos, New lower bounds for the number of \((\le k)\)-edges and the rectilinear crossing number of \(K_n\), Discrete Comput. Geom., 38 (2007), pp. 1-14. · Zbl 1126.52015
[8] O. Aichholzer, T. Hackl, A. Pilz, G. Salazar, and B. Vogtenhuber, Deciding monotonicity of good drawings of the complete graph, in Proc. XVI Spanish Meeting on Computational Geometry (EGC 2015), Barcelona, 2015, pp. 33-36.
[9] A. Arroyo, J. Bensmail, and R. B. Richter, Extending drawings of graphs to arrangements of pseudolines, J. Comput. Geom., 12 (2021), pp. 3-24. · Zbl 1477.68194
[10] A. Arroyo, D. McQuillan, R. B. Richter, and G. Salazar, Levi’s lemma, pseudolinear drawings of \(K_n\), and empty triangles, J. Graph Theory, 87 (2018), pp. 443-459. · Zbl 1388.52018
[11] A. Arroyo, D. McQuillan, R. B. Richter, and G. Salazar, Drawings of \(K_n\) with the same rotation scheme are the same up to triangle-flips (Gioan’s theorem), Australas. J. Combin., 67 (2017), pp. 131-144. · Zbl 1375.05180
[12] A. Arroyo, D. McQuillan, R. B. Richter, and G. Salazar, Convex drawings of \(K_n\): Topology meets geometry, Ars Math. Contemp., to appear. · Zbl 1388.52018
[13] A. Björner, M. Las Vergnas, B. Sturmfelds, N. White, and G. Ziegler, Oriented Matroids, Encyclopedia Math. Appl. 46, Cambridge University Press, 2009.
[14] S. Felsner and M. Scheucher, Arrangements of pseudocircles: On circularizability, Discrete Comput. Geom., 64 (2020), pp. 776-813, https://doi.org/10.1007/s00454-019-00077-y. · Zbl 1450.52017
[15] S. Felsner and M. Scheucher, Homepage of Pseudocircles, https://www3.math.tu-berlin.de/diskremath/pseudocircles/. · Zbl 1520.52014
[16] F. Harary and A. Hill, On the number of crossings in a complete graph, Proc. Edinburgh Math. Soc., 13 (1963), pp. 333-338. · Zbl 0118.18902
[17] J. Kynčl Drawing of Complete Graphs with \(Z(n)\) Crossing,https://mathoverflow.net/questions/128878/drawings-of-complete-graphs-with-zn-crossings, 2013.
[18] L. Lovász, K. Vesztergombi, U. Wagner, and E. Welzl, Convex quadrilaterals and \(k\)-sets, in Towards a Theory of Geometric Graphs, Contemp. Math. 342, Amer. Math. Soc., 2004, pp. 139-148. · Zbl 1071.05028
[19] C. Medina, J. Ramí rez-Alfonsí n, and G. Salazar, The unavoidable arrangements of pseudocircles, Proc. Amer. Math. Soc., 147 (2019), pp. 3165-3175. · Zbl 1422.52010
[20] J. W. Moon, On the distribution of crossings in random complete graphs, J. Soc. Indust. Appl. Math., 13 (1965), pp. 506-510, https://doi.org/10.1137/0113032; Erratum, SIAM J. Appl. Math., 32 (1977), p. 706, https://doi.org/10.1137/0132057. · Zbl 0132.40305
[21] N. H. Rafla, The Good Drawings \(D_n\) of the Complete Graph \(K_n\), Ph.D. thesis, McGill University, Montreal, 1988.
[22] J. Snoeyink and J. Hershberger, Sweeping arrangements of curves, in Discrete and Computational Geometry (New Brunswick, NJ, 1989/1990), DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 6, Amer. Math. Soc., 1991, pp. 309-349. · Zbl 0743.51009
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.