Crossing number, pair-crossing number, and expansion

DOI10.1016/J.JCTB.2003.09.002zbMATH Open1051.05038OpenAlexW2000052110MaRDI QIDQ1880792FDOQ1880792

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

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

zbMATH Keywords

expansiongraph drawingcrossing numberconcurrent multicommodity flowpair-crossing number

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (18)

• 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
• String graphs and incomparability graphs
• On grids in topological graphs
• Title not available (Why is that?)
• Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes
• A Bipartite Strengthening of the Crossing Lemma
• A separator theorem for string graphs and its applications
• Near-optimal separators in string graphs
• On \(k\)-planar crossing numbers
• Odd crossing number and crossing number are not the same
• Crossing Numbers and Cutwidths
• Inserting Multiple Edges into a Planar Graph
• Title not available (Why is that?)
• A Separator Theorem for String Graphs and Its Applications
• A better bound for the pair-crossing number
• Title not available (Why is that?)

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)