Name
Abstract | ||
|---|---|---|
The crossing number ${\mbox{\sc cr}}(G)$ of a graph G is the minimum possible number of edge-crossings in a drawing of G, the pair-crossing number ${\mbox{\sc pair-cr}}(G)$ is the minimum possible number of crossing pairs of edges in a drawing of G, and the odd-crossing number ${\mbox{\sc odd-cr}}(G)$ is the minimum number of pairs of edges that cross an odd number of times. Clearly, ${\mbox{\sc odd-cr}}(G)\le {\mbox{\sc pair-cr}}(G)\le {\mbox{\sc cr}}(G)$. We construct graphs with $0.855\cdot {\mbox{\sc pair-cr}}(G)\ge {\mbox{\sc odd-cr}}(G)$. This improves the bound of Pelsmajer, Schaefer and Štefankovič. Our construction also answers an old question of Tutte. Slightly improving the bound of Valtr, we also show that if the pair-crossing number of G is k, then its crossing number is at most O(k 2/log 2 k). |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/s00454-007-9024-z | Discrete and Computational Geometry |
Keywords | Field | DocType |
Drawings of a graph,Crossing number | Discrete mathematics,Combinatorics,Crossing number (graph theory),Computer science | Conference |
Volume | Issue | ISSN |
39 | 4 | 0179-5376 |
Citations | PageRank | References |
3 | 0.48 | 6 |
Authors | ||
1 | ||