The Degenerate Crossing Number and Higher-Genus Embeddings

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) \leq 3 gcr(G)$, and $dcr(G) = gcr(G)$ as long as $dcr(G) \leq 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. We also 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 NP-complete.

Finally, we extend some of these results to the orientable case (and bundled crossing numbers).

Keywords: degenerate crossing number, non-orientable genus, genus crossing number, bundled crossing number.