The rectilinear local crossing number of K_n

DOI10.1016/J.JCTA.2017.04.003MaRDI QIDQ2363361zbMATH OpenOpenAlexFDO

Authors B. M. Ábrego, Silvia Fernández-Merchant

Publication date 13 July 2017

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

balanced partitioncomplete graphgeometric drawinglocal crossing numberrectilinear crossing numberrectilinear drawing

Mathematics Subject Classification ID

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

Abstract: We determine $$, the rectilinear local crossing number of the complete graph $K_n$ for every $n$. More precisely, for every $notin8,14,$ [ {�ar{ m{lcr}}}(K_n)=leftlceil frac{1}{2} left( n-3-leftlceil frac{n-3}{3} ight ceil ight) leftlceil frac{n-3}{3} ight ceil ight ceil, ] $$, and $$.

Recommendations

• Toward the rectilinear crossing number of \(K _{n}\): New drawings, upper bounds, and asymptotics
• scientific article; zbMATH DE number 1161300
• On the crossing number of complete graphs
• scientific article; zbMATH DE number 1823221
• On the crossing number of complete graphs

Cites work

• 3-symmetric and 3-decomposable geometric drawings of \(K_n\)
• Enumerating order types for small point sets with applications
• Geometric drawings of \(K_{n}\) with few crossings
• On \(\leq k\)-edges, crossings, and halving lines of geometric drawings of \(K _{n }\)
• Rectilinear drawings of graphs
• Reduction of symmetric semidefinite programs using the regular -representation
• The graph crossing number and its variants: a survey
• The rectilinear local crossing number of \(K_{n}\)
• The toroidal crossing number of the complete graph
• Thickness and coarseness of graphs

Cited in

(19)

• Toward the rectilinear crossing number of \(K _{n}\): New drawings, upper bounds, and asymptotics
• On the 2-colored crossing number
• The rectilinear local crossing number of \(K_{n}\)
• The rectilinear crossing number of K_n: closing in (or are we?)
• scientific article; zbMATH DE number 1823221 (Why is no real title available?)
• Bounds for rectilinear crossing numbers
• scientific article; zbMATH DE number 1161300 (Why is no real title available?)
• On the crossing number of complete graphs
• Quantitative restrictions on crossing patterns
• Complexity of geometric \(k\)-planarity for fixed \(k\)
• Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees
• Enumerations of the maximum rectilinear crossing numbers of complete and complete multi-partite graphs
• Rectilinear crossing number of a zero divisor graph
• A note on the maximum rectilinear crossing number of spiders
• The rectilinear crossing number of \(K_{10}\) is 62
• The 3-symmetric pseudolinear crossing number of \(K_{36}\)
• There is a unique crossing-minimal rectilinear drawing of \(K_{18}\)
• Connected matchings
• On polynomials associated to Voronoi diagrams of point sets and crossing numbers

This page was built for publication: The rectilinear local crossing number of \(K_{n}\)

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