Crossing number, pair-crossing number, and expansion

DOI10.1016/J.JCTB.2003.09.002MaRDI QIDQ1880792zbMATH OpenOpenAlexFDO

Authors Petr Kolman, Jiří Matoušek

Publication date 1 October 2004

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2003.09.002

zbMATH Keywords

expansiongraph drawingcrossing numberconcurrent multicommodity flowpair-crossing number

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• A better bound for the pair-crossing number
• A crossing lemma for the pair-crossing number
• scientific article; zbMATH DE number 2084269
• Crossing Numbers and Cutwidths
• Note on the pair-crossing number and the odd-crossing number

Cites work

• scientific article; zbMATH DE number 1054768 (Why is no real title available?)
• scientific article; zbMATH DE number 1452728 (Why is no real title available?)
• scientific article; zbMATH DE number 2119660 (Why is no real title available?)
• A framework for solving VLSI graph layout problems
• Applications of the crossing number
• Bounds for Convex Crossing Numbers
• Combinatorial Geometry and Graph Theory
• Crossing numbers of random graphs
• Crossing-Free Subgraphs
• Expander flows, geometric embeddings and graph partitioning
• Graphs on surfaces
• Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• New lower bound techniques for VLSI
• On VLSI layouts of the star graph and related networks
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• The book crossing number of a graph
• Toward a theory of crossing numbers
• Which crossing number is it anyway?

Cited in

(18)

• scientific article; zbMATH DE number 2084269 (Why is no real title available?)
• Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
• A bipartite strengthening of the crossing Lemma
• The Crossing Number of Graphs: Theory and Computation
• On grids in topological graphs
• String graphs and incomparability graphs
• scientific article; zbMATH DE number 2145247 (Why is no real title available?)
• Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes
• A separator theorem for string graphs and its applications
• A Bipartite Strengthening of the Crossing Lemma
• On \(k\)-planar crossing numbers
• Near-optimal separators in string graphs
• Odd crossing number and crossing number are not the same
• Crossing Numbers and Cutwidths
• Inserting Multiple Edges into a Planar Graph
• scientific article; zbMATH DE number 5019924 (Why is no real title available?)
• A Separator Theorem for String Graphs and Its Applications
• A better bound for the pair-crossing number

This page was built for publication: Crossing number, pair-crossing number, and expansion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1880792)