Name
Abstract | ||
|---|---|---|
It is shown that if a graph of n vertices can be drawn on the torus without edge crossings and the maximum degree of its vertices is at most d, then its planar crossing number cannot exceed cdn, where c is a constant. This bound, conjectured by Brass, cannot be improved, apart from the value of the constant. We strengthen and generalize this result to the case when the graph has a crossing-free drawing on an orientable surface of higher genus and there is no restriction on the degrees of the vertices. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11618058_30 | Graph Drawing |
Keywords | Field | DocType |
maximum degree,crossing number | Graph center,Wheel graph,Discrete mathematics,Graph toughness,Combinatorics,Crossing number (graph theory),Bound graph,Cycle graph,Toroidal graph,Mathematics,Path graph | Conference |
Volume | ISSN | ISBN |
3843 | 0302-9743 | 3-540-31425-3 |
Citations | PageRank | References |
11 | 1.18 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| János Pach | 1 | 2366 | 292.28 |
| Géza Tóth | 2 | 581 | 55.60 |