There is a unique crossing-minimal rectilinear drawing of K₁₈
The rectilinear crossing number \(\overline{\operatorname{cr}}(G)\) of a graph \(G\) is the minimum number of edge crossings in a rectilinear drawing of \(G\) in the plane, i.e., a drawing of \(G\) in the plane where the vertices are points in general position and the edges are straight line segments. A drawing of \(G\) with exactly \(\overline{\operatorname{cr}}(G)\) crossings is called crossing-minimal. In this paper, the authors show that, up to order type isomorphism, there is a unique crossing-minimal rectilinear drawing of \(K_{18}\), namely: Up to order-type isomorphism, there is a unique 18-point set whose induced rectilinear drawing of \(K_{18}\) has \(\overline{\operatorname{cr}}(K_{18})\) crossings. It is easily verified that this drawing does not contain any crossing-minimal drawing of \(K_{17}\). Therefore this settles, in the negative, the following question from \textit{O. Aichholzer} and \textit{H. Krasser} [Comput. Geom. 36, No. 1, 2--15 (2007; Zbl 1110.65019)]: is it true that, for every integer \(n \geq 4\), there exists a crossing-minimal drawing of \(K_n\) that contains a crossing-minimal drawing of \(K_{n-1}\)? A conjecture and an open question conclude the paper.
- There is a unique crossing-minimal rectilinear drawing of \(K_{18}\)
- Toward the rectilinear crossing number of \(K _{n}\): New drawings, upper bounds, and asymptotics
- The rectilinear local crossing number of \(K_{n}\)
- The rectilinear crossing number of \(K_{10}\) is 62
- Geometric drawings of \(K_{n}\) with few crossings
- 3-symmetric and 3-decomposable geometric drawings of \(K_n\)
- A lower bound for the rectilinear crossing number
- Abstract order type extension and new results on the rectilinear crossing number
- 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 \(\leq k\)-edges, crossings, and halving lines of geometric drawings of \(K _{n }\)
- Point sets that minimize \((\leq k)\)-edges, 3-decomposable drawings, and the rectilinear crossing number of \(K_{30}\)
- The rectilinear crossing number of K_n: closing in (or are we?)
- There is a unique crossing-minimal rectilinear drawing of \(K_{18}\)
This page was built for publication: There is a unique crossing-minimal rectilinear drawing of \(K_{18}\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6545086)
