Applications of the crossing number

DOI10.1007/BF02086610zbMath0851.68088OpenAlexW2024937369MaRDI QIDQ1920423

János Pach, Farhad Shahrokhi

Publication date: 12 August 1996

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02086610

zbMATH Keywords

crossing numberbisection width of a graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (39)

Space Crossing Numbers ⋮ Crossing number, pair-crossing number, and expansion ⋮ Crossing numbers of random graphs ⋮ On Compatible Matchings ⋮ \(k\)-planar crossing number of random graphs and random regular graphs ⋮ Coloring curves that cross a fixed curve ⋮ Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes ⋮ A crossing lemma for multigraphs ⋮ On the light side of geometric graphs ⋮ On compatible triangulations with a minimum number of Steiner points ⋮ Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane ⋮ Book embeddings and crossing numbers ⋮ New bounds on the maximum number of edges in \(k\)-quasi-planar graphs ⋮ Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs ⋮ Planar crossing numbers of graphs of bounded genus ⋮ Beyond Outerplanarity ⋮ Orthogonal Tree Decompositions of Graphs ⋮ On compatible matchings ⋮ On the decay of crossing numbers ⋮ Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar ⋮ VIRTUAL CROSSING NUMBERS FOR VIRTUAL KNOTS ⋮ On grids in topological graphs ⋮ Triangle-free geometric intersection graphs with no large independent sets ⋮ A bipartite strengthening of the crossing Lemma ⋮ Unnamed Item ⋮ Two-Planar Graphs Are Quasiplanar ⋮ A Separator Theorem for String Graphs and its Applications ⋮ On-line approach to off-line coloring problems on graphs with geometric representations ⋮ A Bipartite Strengthening of the Crossing Lemma ⋮ Parameterized algorithmics for linear arrangement problems ⋮ Covering nearly surface-embedded graphs with a fixed number of balls ⋮ Experiments on the minimum linear arrangement problem ⋮ Degenerate crossing numbers ⋮ Outerstring Graphs are $\chi$-Bounded ⋮ Quantitative Restrictions on Crossing Patterns ⋮ Quasi-planar Graphs ⋮ 2-Layer k-Planar Graphs ⋮ On the Number of Edges of Fan-Crossing Free Graphs ⋮ A crossing lemma for multigraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding small simple cycle separators for 2-connected planar graphs
• A Turán-type theorem on chords of a convex polygon
• Some geometric applications of Dilworth's theorem
• Quasi-planar graphs have a linear number of edges
• Forcing disjoint segments in the plane
• On compatible triangulations of simple polygons
• A Separator Theorem for Planar Graphs
• On Sets of Distances of n Points
• Disjoint edges in geometric graphs

This page was built for publication: Applications of the crossing number