The Degenerate Crossing Number and HigherGenus EmbeddingsSchaefer, Marcus and Štefankovič, Daniel (2015) The Degenerate Crossing Number and HigherGenus Embeddings. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 2426, 2015 , pp. 6374(Official URL: http://dx.doi.org/10.1007/9783319272610_6). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319272610_6
AbstractIf 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) ≤ 6 gcr(G), and dcr(G) = gcr(G) as long as dcr(G) ≤ 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. 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 NPcomplete.
Actions (login required)
