Point sets that minimize ( k)-edges, 3-decomposable drawings, and the rectilinear crossing number of K₃₀

DOI10.1016/J.DISC.2011.03.030MaRDI QIDQ2275388zbMATH OpenOpenAlexFDO

Authors M. Cetina, César Hernández-Vélez, J. Leaños, Maria Cristina Villalobos

Publication date 8 August 2011

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

3-decomposability\(k\)-edgesrectilinear crossing number

Mathematics Subject Classification ID

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

Abstract: There are two properties shared by all known crossing-minimizing geometric drawings of $K_n$, for $n$ a multiple of 3. First, the underlying $n$-point set of these drawings has exactly $$ $(lek)$-edges, for all $0lek<n/3$. Second, all such drawings have the $n$ points divided into three groups of equal size; this last property is captured under the concept of 3-decomposability. In this paper we show that these properties are tightly related: every $n$-point set with exactly $$ $(lek)$-edges for all $0lek<n/3$, is 3-decomposable. As an application, we prove that the rectilinear crossing number of $K_{30}$ is 9726.

Recommendations

• 3-symmetric and 3-decomposable geometric drawings of \(K_n\)
• On \(\leq k\)-edges, crossings, and halving lines of geometric drawings of \(K _{n }\)
• New lower bounds for the number of \((\leq k)\)-edges and the rectilinear crossing number of \(K_{n}\)
• Computational search of small point sets with small rectilinear crossing number
• Toward the rectilinear crossing number of \(K _{n}\): New drawings, upper bounds, and asymptotics

Cites work

• 3-symmetric and 3-decomposable geometric drawings of \(K_n\)
• \(k\)-sets, convex quadrilaterals, and the rectilinear crossing number of \(K_{n}\)
• A lower bound for the rectilinear crossing number
• Abstract order type extension and new results on the rectilinear crossing number
• An extended lower bound on the number of( k)-edges to generalized configurations of points and the pseudolinear crossing number of K_n
• scientific article; zbMATH DE number 2145237 (Why is no real title available?)
• 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
• The maximum number of halving lines and the rectilinear crossing number of for

Cited in

(6)

• The 2-page crossing number of \(K_{n}\)
• On \(\leq k\)-edges, crossings, and halving lines of geometric drawings of \(K _{n }\)
• New algorithms and bounds for halving pseudolines
• The 3-symmetric pseudolinear crossing number of \(K_{36}\)
• There is a unique crossing-minimal rectilinear drawing of \(K_{18}\)
• 3-symmetric and 3-decomposable geometric drawings of \(K_n\)

This page was built for publication: Point sets that minimize \((\leq k)\)-edges, 3-decomposable drawings, and the rectilinear crossing number of \(K_{30}\)

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