Odd Crossing Number and Crossing Number Are Not the Same
| Autor: | Marcus Schaefer, Daniel Stefankovic, Michael J. Pelsmajer |
|---|---|
| Rok vydání: | 2008 |
| Předmět: |
Discrete mathematics
Clockwise order The Intersect 1-planar graph Graph Theoretical Computer Science Combinatorics Dehn twist Computational Theory and Mathematics Odd graph Rotation system Discrete Mathematics and Combinatorics Geometry and Topology Crossing number (graph theory) MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Discrete & Computational Geometry. 39:442-454 |
| ISSN: | 1432-0444 0179-5376 |
| DOI: | 10.1007/s00454-008-9058-x |
| Popis: | The crossing number of a graph is the minimum number of edge intersections in a plane drawing of a graph, where each intersection is counted separately. If instead we count the number of pairs of edges that intersect an odd number of times, we obtain the odd crossing number. We show that there is a graph for which these two concepts differ, answering a well-known open question on crossing numbers. To derive the result we study drawings of maps (graphs with rotation systems). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink