Approximating the rectilinear crossing number

DOI10.1007/978-3-319-50106-2_32MaRDI QIDQ2961535zbMATH OpenOpenAlexFDO

Authors Jacob Fox, János Pach, Andrew Suk

Publication date 21 February 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.03753, http://real.mtak.hu/102412/1/1606.03753

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: A straight-line drawing of a graph $G$ is a mapping which assigns to each vertex a point in the plane and to each edge a straight-line segment connecting the corresponding two points. The rectilinear crossing number of a graph $G$, $overlinecr(G)$, is the minimum number of crossing edges in any straight-line drawing of $G$. Determining or estimating $overlinecr(G)$ appears to be a difficult problem, and deciding if $overlinecr(G)leqk$ is known to be NP-hard. In fact, the asymptotic behavior of $overlinecr(K_n)$ is still unknown. In this paper, we present a deterministic $n^{2+o(1)}$-time algorithm that finds a straight-line drawing of any $n$-vertex graph $G$ with $overlinecr(G)+o(n^4)$ crossing edges. Together with the well-known Crossing Lemma due to Ajtai et al. and Leighton, this result implies that for any dense $n$-vertex graph $G$, one can efficiently find a straight-line drawing of $G$ with $(1+o(1))overlinecr(G)$ crossing edges.

Recommendations

• Approximating the rectilinear crossing number
• Approximating the maximum rectilinear crossing number
• Toward the rectilinear crossing number of \(K _{n}\): New drawings, upper bounds, and asymptotics
• An algorithm for the graph crossing number problem
• Some provably hard crossing number problems

Cites work

• scientific article; zbMATH DE number 431988 (Why is no real title available?)
• scientific article; zbMATH DE number 5485473 (Why is no real title available?)
• scientific article; zbMATH DE number 1452728 (Why is no real title available?)
• scientific article; zbMATH DE number 3047038 (Why is no real title available?)
• Abstract order type extension and new results on the rectilinear crossing number
• An algorithm for the graph crossing number problem
• An optimal algorithm for finding Frieze-Kannan regular partitions
• Bounds for graph regularity and removal lemmas
• Bounds for rectilinear crossing numbers
• Complexity of some geometric and topological problems
• Computational search of small point sets with small rectilinear crossing number
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Crossing numbers of random graphs
• Crossing-Free Subgraphs
• Density and regularity theorems for semi-algebraic hypergraphs
• Efficient Planarity Testing
• Enumerating order types for small point sets with applications
• Expander flows, geometric embeddings and graph partitioning
• Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas
• Large networks and graph limits
• Lower bounds of tower type for Szemerédi's uniformity lemma
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Multidimensional Sorting
• On \(\leq k\)-edges, crossings, and halving lines of geometric drawings of \(K _{n }\)
• On the combinatorial and algebraic complexity of quantifier elimination
• Quasi-random graphs
• Quick approximation to matrices and applications
• Ramsey theory, integer partitions and a new proof of the Erdős-Szekeres theorem
• Some provably hard crossing number problems
• The Rectilinear Crossing Number of a Complete Graph and Sylvester's "Four Point Problem" of Geometric Probability
• The graph crossing number and its variants: a survey
• The rectilinear crossing number of \(K_n\): closing in (or are we?)

Cited in

(14)

• Crossing number for graphs with bounded pathwidth
• Crossing numbers and stress of random graphs
• Asymptotics for numbers of line segments and lines in a square grid
• On the Pseudolinear Crossing Number
• Approximating the rectilinear crossing number
• Approximating the maximum rectilinear crossing number
• Computational search of small point sets with small rectilinear crossing number
• Limiting Crossing Numbers for Geodesic Drawings on the Sphere
• Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees
• Bounds for Convex Crossing Numbers
• An Ongoing Project to Improve the Rectilinear and the Pseudolinear Crossing Constants
• Computing crossing numbers in quadratic time
• scientific article; zbMATH DE number 7278018 (Why is no real title available?)
• Weighted Turán problems with applications

This page was built for publication: Approximating the rectilinear crossing number

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