The Degenerate Crossing Number and Higher-Genus Embeddings

Schaefer, Marcus and Štefankovič, Daniel (2015) The Degenerate Crossing Number and Higher-Genus Embeddings. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015 , pp. 63-74(Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_6).

Full text not available from this repository.

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) ≤ 6 gcr(G), and dcr(G) = gcr(G) as long as dcr(G) ≤ 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 NP-complete.

Item Type: Conference Paper
Keywords: Degenerate crossing number Non-orientable genus Genus crossing number
Classifications: G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.999 Others
M Methods > M.100 Algebraic
Z Theory > Z.750 Topology
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 04 May 2016 16:19
Last Modified: 04 May 2016 16:19
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1478

Actions (login required)

View Item View Item