Approximating the rectilinear crossing number

DOI10.1007/978-3-319-50106-2_32zbMATH Open1478.68234arXiv1606.03753OpenAlexW2441637932MaRDI QIDQ2961535FDOQ2961535

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)

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.

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

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

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)

Cites Work

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

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
• Computational search of small point sets with small rectilinear crossing number
• Approximating the maximum 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
• Title not available (Why is that?)
• Computing crossing numbers in quadratic time
• 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)