Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00580
The Degenerate Crossing Number and HigherGenus Embeddings
Vol. 26, no. 1, pp. 3558, 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 wellknown 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 (singlevertex) 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 NPcomplete. Finally, we extend some of these results to the orientable case (and bundled crossing numbers). Keywords: degenerate crossing number, nonorientable genus, genus crossing number, bundled crossing number.
This work is licensed under the terms of the CCBY 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

Journal Supporters
