Convex drawings of the complete graph: topology meets geometry

DOI10.26493/1855-3974.2134.AC9zbMATH Open1492.05104arXiv1712.06380OpenAlexW3213073008WikidataQ114040697 ScholiaQ114040697MaRDI QIDQ5089707FDOQ5089707

Authors: Alan Arroyo, Daniel McQuillan, R. B. Richter, Gelasio Salazar 

Publication date: 15 July 2022

Published in: Ars Mathematica Contemporanea (Search for Journal in Brave)

Abstract: In this work, we introduce and develop a theory of convex drawings of the complete graph $K_n$ in the sphere. A drawing $D$ of $K_n$ is convex if, for every 3-cycle $T$ of $K_n$, there is a closed disc $Delt{a}_T$ bounded by $D[T]$ such that, for any two vertices $u,v$ with $D[u]$ and $D[v]$ both in $Delt{a}_T$, the entire edge $D[uv]$ is also contained in $Delt{a}_T$. As one application of this perspective, we consider drawings containing a non-convex $K_5$ that has restrictions on its extensions to drawings of $K_7$. For each such drawing, we use convexity to produce a new drawing with fewer crossings. This is the first example of local considerations providing sufficient conditions for suboptimality. In particular, we do not compare the number of crossings {with the number of crossings in} any known drawings. This result sheds light on Aichholzer's computer proof (personal communication) showing that, for $nle12$, every optimal drawing of $K_n$ is convex. Convex drawings are characterized by excluding two of the five drawings of $K_5$. Two refinements of convex drawings are h-convex and f-convex drawings. The latter have been shown by Aichholzer et al (Deciding monotonicity of good drawings of the complete graph, Proc.~XVI Spanish Meeting on Computational Geometry (EGC 2015), 2015) and, independently, the authors of the current article (Levi's Lemma, pseudolinear drawings of $K_n$, and empty triangles, br{J. Graph Theory DOI: 10.1002/jgt.22167)}, to be equivalent to pseudolinear drawings. Also, h-convex drawings are equivalent to pseudospherical drawings as demonstrated recently by Arroyo et al (Extending drawings of complete graphs into arrangements of pseudocircles, submitted).

Full work available at URL: https://arxiv.org/abs/1712.06380

Recommendations

• scientific article; zbMATH DE number 5238988
• Bounds for Convex Crossing Numbers
• scientific article; zbMATH DE number 2145245
• Topological drawings meet classical theorems from convex geometry
• Levi's Lemma, pseudolinear drawings of , and empty triangles

zbMATH Keywords

complete graphsconvex drawingssimple drawings

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Empty Simplices in Euclidean Space
• Planar point sets with a small number of empty convex polygons
• Title not available (Why is that?)
• Title not available (Why is that?)
• Unavoidable configurations in complete topological graphs
• Title not available (Why is that?)
• On the crossing number of \(K_n\) without computer assistance
• On the crossing number of \(K_{13}\)
• On Convex Polygons Determined by a Finite Planar Set
• On the Erdős-Szekeres convex polygon problem
• On the Number of Crossings in a Complete Graph
• A note on the parity of the number of crossings of a graph
• Empty triangles in drawings of the complete graph
• Empty triangles in good drawings of the complete graph
• The early history of the brick factory problem
• Levi's Lemma, pseudolinear drawings of , and empty triangles
• Closing in on Hill's conjecture
• Extending drawings of complete graphs into arrangements of pseudocircles

Cited In (10)

• Closing in on Hill's conjecture
• Drawing polytopal graphs with {\texttt{polymake}}
• Topological drawings meet classical theorems from convex geometry
• Topological Drawings of Complete Bipartite Graphs
• Convex parity graphs
• Towards crossing-free Hamiltonian cycles in simple drawings of complete graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The topological drawing of a graph: construction methods

This page was built for publication: Convex drawings of the complete graph: topology meets geometry

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5089707)