3-symmetric and 3-decomposable geometric drawings of K_n

DOI10.1016/J.DAM.2009.09.020MaRDI QIDQ987669zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

\(k\)-setsgeometric drawingsrectilinear crossing numberssymmetric drawings

Mathematics Subject Classification ID

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

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.

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}\)

Cites work

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

Cited in

(11)

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

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)