Archdeacon conjecture bounds nonplanar quadruples in rotation systems
Some results on Archdeacon's conjecture for rotation systems
Computational Geometry
Summary
A rotation system arranges elements so their connections have a circular order. The paper studies how many groups of four elements must create some unavoidable 'crossings' in such systems, a problem linked to drawing complete graphs without overlaps. The authors confirm a longstanding conjecture for small sizes using computers and provide approximate bounds for larger sizes, partly by hand. They also prove the conjecture for a certain special class of these systems. This helps understand the limits of how 'tangled' such arrangements must be.
What this means in practice
- •For graph drawing software developers: Use lower bounds on unavoidable crossings in rotation systems to improve algorithms that optimize graph visualizations.
- •For combinatorial optimization teams: Incorporate proven bounds on rotation systems to guide heuristics for minimizing edge crossings in network diagrams and layout problems.
A theory result. No direct application yet.
Authors
Arahat Chikkatur, Ji Zeng
Abstract
A rotation system on $n$ elements assigns to each element a cyclic order of the other $n-1$ elements. A four-element subset is non-planar if its induced rotation system cannot be realized by a crossing-free drawing of $K_4$. As a combinatorial strengthening of Hill's conjecture on the crossing number of the complete graph, Archdeacon conjectured that every rotation system on $n$ elements has at least $H(n)=\frac{1}{4} \lfloor\frac {n}{2}\rfloor \lfloor\frac{n-1}{2}\rfloor \lfloor\frac{n-2}{2}\rfloor \lfloor\frac{n-3}{2}\rfloor$ non-planar four-element subsets. We computationally verify Archdeacon's conjecture for $n\leq 10$ and show that every extremal rotation system in these orders is realizable by a simple drawing. With computer assistance, we prove that every rotation system on $n$ elements has at least $(8/9 - o(1)) H(n)$ non-planar four-element subsets. We also present a proof by hand for a weaker lower bound of $(2/3-o(1)) H(n)$. Finally, extending recent work of Felsner on antipodal pairs in drawings, we show that Archdeacon's conjecture holds for antipodally shellable rotation systems.