2015 | OriginalPaper | Buchkapitel
The Degenerate Crossing Number and Higher-Genus Embeddings
Autoren: Marcus Schaefer, Daniel Štefankovič
Erschienen in:
Graph Drawing and Network Visualization
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, dcr(G), 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, gcr(G), of G equals the smallest number k so that G has an embedding in a surface with k crosscaps. The question then becomes whether dcr(G) = gcr(G), and it is in this form that it was first asked by Mohar.
We show that dcr(G) \(\le \) 6 gcr(G), and dcr(G) = gcr(G) as long as dcr(G) \(\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.
