Space Crossing Numbers

DOI10.1017/S096354831100040XzbMath1242.05062arXiv1102.1275OpenAlexW2338992247MaRDI QIDQ2888867

Alfredo Hubard, Boris Bukh

Publication date: 4 June 2012

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

pseudo-random graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

On Erd\H{o}s Chains in the Plane ⋮ Crossings in grid drawings ⋮ A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing ⋮ An extension of a theorem of Yao and Yao ⋮ On grids in point-line arrangements in the plane ⋮ On Grids in Point-Line Arrangements in the Plane

Cites Work

• Lower bounds for weak epsilon-nets and stair-convexity
• On the Yao-Yao partition theorem
• Small topological complete subgraphs of ``dense graphs
• Graphs drawn with few crossings per edge
• Judicious partitions of graphs
• A positive fraction Erdős-Szekeres theorem
• Improved bounds for planar \(k\)-sets and related problems
• The Tverberg-Vrećica problem and the combinatorial geometry on vector bundles
• Applications of the crossing number
• Tverberg's transversal conjecture and analogues of nonembeddability theorems for transversals
• Knots and links in spatial graphs
• LINES JOINING COMPONENTS OF A LINK
• New lower bound techniques for VLSI
• Bounds for rectilinear crossing numbers
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• Algorithms in real algebraic geometry