General lower bounds for the minor crossing number of graphs

DOI10.1007/S00454-010-9245-4MaRDI QIDQ5962348zbMATH OpenOpenAlexFDO

Authors Drago Bokal, Éva Czabarka, László A. Székely, Imrich Vrt'o

Publication date 22 September 2010

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

Full work available at URL https://doi.org/10.1007/s00454-010-9245-4

zbMATH Keywords

bisection methodgraph minorcrossing numberembedding methodcrossing lemmaHypercubestring graphsminor crossing number

Mathematics Subject Classification ID

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

Recommendations

• Graph minors and the crossing number of graphs
• The Minor Crossing Number
• Improved upper bounds on the crossing number
• The minor crossing number of graphs with an excluded minor
• Minor-monotone crossing number

Cites work

• scientific article; zbMATH DE number 1188564 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• A separator theorem for graphs of bounded genus
• Bounding the crossing number of a graph in terms of the crossing number of a minor with small maximum degree
• Crossing Number Problems
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• Crossing-Free Subgraphs
• Decidability of string graphs
• Edge separators for graphs of bounded genus with applications
• Expansion and isoperimetric constants for product graphs
• Graphs on surfaces
• Improving the crossing lemma by finding more crossings in sparse graphs
• Intersections of curve systems and the crossing number of \(C_ 5\times C_ 5\)
• Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus
• Matchings and paths in the cube
• New bounds on crossing numbers
• On the crossing numbers of Cartesian products with trees
• Optimal meshes of curves in the Klein bottle
• Recognizing string graphs in NP
• Recognizing string graphs is decidable
• String graphs requiring exponential representations
• String graphs. I: The number of critical nonstring graphs is infinite
• String graphs. II: Recognizing string graphs is NP-hard
• The Minor Crossing Number
• The crossing number of a graph on a compact 2-manifold
• The crossing number ofC5 �Cn
• The minor crossing number of graphs with an excluded minor
• Topology of Thin Film RC Circuits

Cited in

(6)

• The Minor Crossing Number
• Minor-monotone crossing number
• A circle criterion for a generalized cross graph in terms of minimal excluded minors
• The minor crossing number of graphs with an excluded minor
• Crossing number additivity over edge cuts
• Graph minors and the crossing number of graphs

This page was built for publication: General lower bounds for the minor crossing number of graphs

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