Computational search of small point sets with small rectilinear crossing number

DOI10.7155/JGAA.00328MaRDI QIDQ5494864zbMATH OpenOpenAlexFDO

Authors

Publication date 30 July 2014

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

rectilinear drawings

Mathematics Subject Classification ID

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

Abstract: Let $crs(K_n)$ be the minimum number of crossings over all rectilinear drawings of the complete graph on $n$ vertices on the plane. In this paper we prove that $$; improving thus on the previous best known upper bound. This is done by obtaining new rectilinear drawings of $K_n$ for small values of $n$, and then using known constructions to obtain arbitrarily large good drawings from smaller ones. The "small" sets where found using a simple heuristic detailed in this paper.

Recommendations

• A Geometric Heuristic for Rectilinear Crossing Minimization
• Construction of some computational algorithms on finite sets of points in the plane
• Efficient construction of a small hitting set for combinatorial rectangles in high dimension
• Approximating the rectilinear crossing number
• Approximating the rectilinear crossing number
• Approximating the maximum rectilinear crossing number
• scientific article; zbMATH DE number 7525513
• scientific article; zbMATH DE number 2081026
• A lower bound for the rectilinear crossing number
• scientific article; zbMATH DE number 125273

Cited in

(11)

• On the 2-colored crossing number
• New algorithms and bounds for halving pseudolines
• Approximating the rectilinear crossing number
• Approximating the rectilinear crossing number
• On \(k\)-planar crossing numbers
• An Ongoing Project to Improve the Rectilinear and the Pseudolinear Crossing Constants
• On the rectilinear crossing number of complete uniform hypergraphs
• scientific article; zbMATH DE number 5019924 (Why is no real title available?)
• Point sets that minimize \((\leq k)\)-edges, 3-decomposable drawings, and the rectilinear crossing number of \(K_{30}\)
• scientific article; zbMATH DE number 7525513 (Why is no real title available?)
• Counting the number of crossings in geometric graphs

This page was built for publication: Computational search of small point sets with small rectilinear crossing number

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