General Lower Bounds for the Minor Crossing Number of Graphs

There are three general lower bound techniques for the crossing numbers of graphs: the Crossing Lemma, the bisection method and the embedding method. In this contribution, we present their adaptations to the minor crossing number. Using the adapted bounds, we improve on the known bounds on the minor...

Full description

Saved in:
Bibliographic Details
Published in:Discrete & computational geometry 2010-09, Vol.44 (2), p.463-483
Main Authors: Bokal, Drago, Czabarka, Éva, Székely, László A., Vrt’o, Imrich
Format: Article
Language:English
Subjects:
Adaptation
Combinatorics
Computational geometry
Computational Mathematics and Numerical Analysis
Geometry
Graph theory
Graphs
Hypercubes
Lower bounds
Mathematics
Mathematics and Statistics
Strings
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:There are three general lower bound techniques for the crossing numbers of graphs: the Crossing Lemma, the bisection method and the embedding method. In this contribution, we present their adaptations to the minor crossing number. Using the adapted bounds, we improve on the known bounds on the minor crossing number of hypercubes. We also point out relations of the minor crossing number to string graphs and establish a lower bound for the standard crossing number in terms of Randič index.
ISSN:0179-5376
1432-0444
DOI:10.1007/s00454-010-9245-4