Name
Abstract | ||
|---|---|---|
If a graph embeds in a surface with k crosscaps, does it always have an embedding in the same surface in which every edge passes through each crosscap at most once? This well-known open problem can be restated using crossing numbers: the degenerate crossing number, dcrG, of G equals the smallest number k so that G has an embedding in a surface with k crosscaps in which every edge passes through each crosscap at most once. The genus crossing number, gcrG, of G equals the smallest number k so that G has an embedding in a surface with k crosscaps. The question then becomes whether dcrG = gcrG, and it is in this form that it was first asked by Mohar. We show that dcrG$$\\le $$ 6 gcrG, and dcrG = gcrG as long as dcrG$$\\le $$ 3. We can separate dcr and gcr for single-vertex graphs with embedding schemes, but it is not clear whether the separating example can be extended into separations on simple graphs. Finally, we show that if a graph can be embedded in a surface with crosscaps, then it has an embedding in that surface in which every edge passes through each crosscap at most twice. This implies that dcr is $$\\mathrm {\\mathbf {NP}}$$-complete. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-319-27261-0_6 | Graph Drawing |
Keywords | Field | DocType |
Degenerate crossing number, Non-orientable genus, Genus crossing number | Graph,Degenerate energy levels,Discrete mathematics,Combinatorics,Embedding,Crossing number (graph theory),Open problem,Mathematics | Conference |
Volume | ISSN | Citations |
9411 | 0302-9743 | 1 |
PageRank | References | Authors |
0.35 | 3 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marcus Schaefer | 1 | 86 | 5.27 |
| Daniel Stefankovic | 2 | 243 | 28.65 |