3-symmetric and 3-decomposable geometric drawings of K_n

DOI10.1016/J.DAM.2009.09.020zbMATH Open1228.05214arXiv0805.0016OpenAlexW1986278299MaRDI QIDQ987669FDOQ987669

Authors: M. Cetina, B. M. Ábrego, Silvia Fernández-Merchant, J. Leaños, Gelasio Salazar 

Publication date: 13 August 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: Even the most superficial glance at the vast majority of crossing-minimal geometric drawings of $K_n$ reveals two hard-to-miss features. First, all such drawings appear to be 3-fold symmetric (or simply {em 3-symmetric}) . And second, they all are {em 3-decomposable}, that is, there is a triangle $T$ enclosing the drawing, and a balanced partition $A,B,C$ of the underlying set of points $P$, such that the orthogonal projections of $P$ onto the sides of $T$ show $A$ between $B$ and $C$ on one side, $B$ between $A$ and $C$ on another side, and $C$ between $A$ and $B$ on the third side. In fact, we conjecture that all optimal drawings are 3-decomposable, and that there are 3-symmetric optimal constructions for all $n$ multiple of 3. In this paper, we show that any 3-decomposable geometric drawing of $K_n$ has at least $$ crossings. On the other hand, we produce 3-symmetric and 3-decomposable drawings that improve the {em general} upper bound for the rectilinear crossing number of $K_n$ to $$. We also give explicit 3-symmetric and 3-decomposable constructions for $n<100$ that are at least as good as those previously known.

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

Recommendations

• Point sets that minimize \((\leq k)\)-edges, 3-decomposable drawings, and the rectilinear crossing number of \(K_{30}\)
• Geometric drawings of \(K_{n}\) with few crossings
• Toward the rectilinear crossing number of \(K _{n}\): New drawings, upper bounds, and asymptotics
• On \(\leq k\)-edges, crossings, and halving lines of geometric drawings of \(K _{n }\)
• There is a unique crossing-minimal rectilinear drawing of \(K_{18}\)

zbMATH Keywords

\(k\)-setsgeometric drawingsrectilinear crossing numberssymmetric drawings

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Research Problems in Discrete Geometry
• Title not available (Why is that?)
• Geometric drawings of \(K_{n}\) with few crossings
• On the combinatorial classification of nondegenerate configurations in the plane
• New lower bounds for the number of \((\leq k)\)-edges and the rectilinear crossing number of \(K_{n}\)
• \(k\)-sets, convex quadrilaterals, and the rectilinear crossing number of \(K_{n}\)
• A lower bound for the rectilinear crossing number
• New results on lower bounds for the number of (⩽ k)-facets
• The maximum number of halving lines and the rectilinear crossing number of for
• A central approach to bound the number of crossings in a generalized configuration
• Crossing Number Problems
• On the crossing number of complete graphs
• Toward the rectilinear crossing number of \(K _{n}\): New drawings, upper bounds, and asymptotics

Cited In (11)

• Geometric achromatic and pseudoachromatic indices
• There is a unique crossing-minimal rectilinear drawing of \(K_{18}\)
• On \(\leq k\)-edges, crossings, and halving lines of geometric drawings of \(K _{n }\)
• The 3-symmetric pseudolinear crossing number of \(K_{36}\)
• The rectilinear local crossing number of \(K_{n}\)
• Disjointness graphs of segments in \(\mathbb{R}^2\) are almost all Hamiltonian
• From art and circuit design to geometry and combinatorics
• On crossing numbers of geometric proximity graphs
• An Ongoing Project to Improve the Rectilinear and the Pseudolinear Crossing Constants
• Point sets that minimize \((\leq k)\)-edges, 3-decomposable drawings, and the rectilinear crossing number of \(K_{30}\)
• The 2-page crossing number of \(K_{n}\)

This page was built for publication: 3-symmetric and 3-decomposable geometric drawings of \(K_n\)

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