Improving the crossing lemma by finding more crossings in sparse graphs

DOI10.1007/s00454-006-1264-9zbMath1104.05022OpenAlexW1993083969WikidataQ56454600 ScholiaQ56454600MaRDI QIDQ854708

János Pach, Radoš Radoičić, Gábor Tardos, Géza Tóth

Publication date: 6 December 2006

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-006-1264-9

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (50)

The Szemerédi-Trotter theorem in the complex plane ⋮ Improvement on the decay of crossing numbers ⋮ Drawing Graphs with Right Angle Crossings ⋮ Edge-minimum saturated \(k\)-planar drawings ⋮ Recognizing and embedding simple optimal 2-planar graphs ⋮ On the Decay of Crossing Numbers of Sparse Graphs ⋮ The crossing number of twisted graphs ⋮ On topological graphs with at most four crossings per edge ⋮ A solution to a problem of Grünbaum and Motzkin and of Erdős and Purdy about bichromatic configurations of points in the plane ⋮ Crossing by lines all edges of a line arrangement ⋮ Crossings between non-homotopic edges ⋮ Crossings in grid drawings ⋮ Progress on Dirac's conjecture ⋮ Algorithms for Colourful Simplicial Depth and Medians in the Plane ⋮ On the existence of ordinary triangles ⋮ Graphs that admit right angle crossing drawings ⋮ On the Density of Non-simple 3-Planar Graphs ⋮ On the Number of Tetrahedra with Minimum, Unit, and Distinct Volumes in Three-Space ⋮ Note on \(k\)-planar crossing numbers ⋮ On crossing numbers of geometric proximity graphs ⋮ Efficient generation of different topological representations of graphs beyond-planarity ⋮ On \(\leq k\)-edges, crossings, and halving lines of geometric drawings of \(K _{n }\) ⋮ Planar crossing numbers of graphs of bounded genus ⋮ Gap-Planar Graphs ⋮ On the \(k\)-planar local crossing number ⋮ Efficient Generation of Different Topological Representations of Graphs Beyond-Planarity ⋮ Szemerédi-Trotter-type theorems in dimension 3 ⋮ Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar ⋮ Trapezoids and deltoids in wide planar point sets ⋮ A bipartite strengthening of the crossing Lemma ⋮ Two-Planar Graphs Are Quasiplanar ⋮ Drawing graphs with right angle crossings ⋮ Unnamed Item ⋮ Graphs that Admit Right Angle Crossing Drawings ⋮ On RAC drawings of graphs with one bend per edge ⋮ Light edges in 3-connected 2-planar graphs with prescribed minimum degree ⋮ Gap-planar graphs ⋮ On RAC drawings of graphs with one bend per edge ⋮ Testing gap \(k\)-planarity is NP-complete ⋮ A Bipartite Strengthening of the Crossing Lemma ⋮ Improvement on the Decay of Crossing Numbers ⋮ A survey of graphs with known or bounded crossing numbers ⋮ Quantitative Restrictions on Crossing Patterns ⋮ $$\textit{\textbf{k}}$$-Planar Graphs ⋮ Right Angle Crossing Drawings of Graphs ⋮ Crossing lemma for the odd-crossing number ⋮ Crossings Between Non-homotopic Edges ⋮ Simple Topological Drawings of k-Planar Graphs ⋮ 2-Layer k-Planar Graphs ⋮ On the Number of Edges of Fan-Crossing Free Graphs

This page was built for publication: Improving the crossing lemma by finding more crossings in sparse graphs