Applications of the crossing number
From MaRDI portal
Publication:1920423
DOI10.1007/BF02086610zbMath0851.68088OpenAlexW2024937369MaRDI QIDQ1920423
János Pach, Mario Szegedy, 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
Related Items
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
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
