General Lower Bounds for the Minor Crossing Number of Graphs
| Autor: | Éva Czabarka, László A. Székely, Drago Bokal, Imrich Vrto |
|---|---|
| Rok vydání: | 2010 |
| Předmět: |
Discrete mathematics
Lemma (mathematics) String (computer science) Minor (linear algebra) Upper and lower bounds Theoretical Computer Science Combinatorics Computational Theory and Mathematics Bisection method Graph minor Discrete Mathematics and Combinatorics Embedding Geometry and Topology Crossing number (graph theory) Mathematics |
| Zdroj: | Discrete & Computational Geometry. 44:463-483 |
| ISSN: | 1432-0444 0179-5376 |
| DOI: | 10.1007/s00454-010-9245-4 |
| Popis: | 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 Randic index. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink