Approximating the rectilinear crossing number

DOI10.1016/j.comgeo.2019.04.003zbMath1431.90162OpenAlexW2937270620WikidataQ128030737 ScholiaQ128030737MaRDI QIDQ2331210

Andrew Suk, Jacob Fox, János Pach

Publication date: 25 October 2019

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: http://real.mtak.hu/102412/1/1606.03753

zbMATH Keywords

quasi-random graphscrossing numberstraight-line drawingsregularity lemmas

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items

Crossing Numbers of Beyond-Planar Graphs Revisited, Parameterized analysis and crossing minimization problems, Exact crossing number parameterized by vertex cover

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On \(\leq k\)-edges, crossings, and halving lines of geometric drawings of \(K _{n }\)
• A short proof of Gowers' lower bound for the regularity lemma
• 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 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