Journal of Graph Algorithms and Applications
|Home||Issues||About JGAA||Instructions for Authors|
The Degenerate Crossing Number and Higher-Genus Embeddings
Vol. 26, no. 1, pp. 35-58, 2022. Regular paper.
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.
This work is licensed under the terms of the CC-BY license.
Submitted: December 2016.
Reviewed: January 2018.
Revised: April 2019.
Reviewed: August 2020.
Revised: October 2021.
Accepted: December 2021.
Final: December 2021.
Published: January 2022.
Communicated by Petra Mutzel