Approximating the Rectilinear Crossing Number

DOI10.1007/978-3-319-50106-2_32zbMath1478.68234arXiv1606.03753OpenAlexW2441637932MaRDI QIDQ2961535

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

Mathematics Subject Classification ID

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

Related Items

Crossing numbers and stress of random graphs, Crossing number for graphs with bounded pathwidth, Unnamed Item, Weighted Turán problems with applications, Reconstruction of the Crossing Type of a Point Set from the Compatible Exchange Graph of Noncrossing Spanning Trees

Cites Work

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