Computational search of small point sets with small rectilinear crossing number

DOI10.7155/JGAA.00328zbMATH Open1295.05162arXiv1403.1288OpenAlexW2963030908MaRDI QIDQ5494864FDOQ5494864

Authors:

Publication date: 30 July 2014

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

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.

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

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

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)

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
• Title not available (Why is that?)
• Point sets that minimize \((\leq k)\)-edges, 3-decomposable drawings, and the rectilinear crossing number of \(K_{30}\)
• Title not available (Why is that?)
• 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)