General lower bounds for the minor crossing number of graphs

DOI10.1007/S00454-010-9245-4zbMATH Open1194.05024OpenAlexW2079621156MaRDI QIDQ5962348FDOQ5962348

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

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

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

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)

Cites Work

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

Cited In (5)

• 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
• The Minor Crossing Number

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)