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, Los Angeles, CA, USA , 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
ID Code:1478

Repository Staff Only: item control page

References

Ackerman, E., Pinchasi, R.: On the degenerate crossing number. Discrete Comput. Geom. 49(3), 695–702 (2013)

Cairns, G., Nikolayevsky, Y.: Bounds for generalized thrackles. Discrete Comput. Geom. 23(2), 191–206 (2000)

Dey, T.K., Schipper, H.: A new technique to compute polygonal schema for 2-manifolds with application to null-homotopy detection. Discrete Comput. Geom. 14(1), 93–110 (1995)

Duncan, C.A., Goodrich, M.T., Kobourov, S.G.: Planar drawings of higher-genus graphs. J. Graph Algorithms Appl. 15(1), 7–32 (2011)

Erickson, J., Har-Peled, S.: Optimally cutting a surface into a disk. Discrete Comput. Geom. 31(1), 37–59 (2004). ACM Symposium on Computational Geometry, Barcelona 2002

Harborth, H.: Drawings of graphs and multiple crossings. In: Alavi, Y., Chartrand, G., Lick, D.R., Wall, C.E., Lesniak, L. (eds.) Graph Theory with Applications to Algorithms and Computer Science (Kalamazoo, Mich., 1984), pp. 413–421. Wiley-Interscience Publication, New York (1985)

Lazarus, F., Pocchiola, M., Vegter, G., Verroust, A.: Computing a canonical polygonal schema of an orientable triangulated surface. In: Proceedings of the Seventeenth Annual Symposium on Computational Geometry (SCG-01), pp. 80–89. ACM Press, New York, 3–5 2001

Mohar, B.: The genus crossing number. Ars Math. Contemp. 2(2), 157–162 (2009)

Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD (2001)

Pach, J., Tóth, G.: Degenerate crossing numbers. Discrete Comput. Geom. 41(3), 376–384 (2009)

Pelsmajer, M.J., Schaefer, M., Štefankovič, D.: Removing even crossings on surfaces. European J. Combin. 30(7), 1704–1717 (2009)

Schaefer, M.: The graph crossing number and its variants: a survey. Electron. J. Comb. 20, 1–90 (2013). Dynamic Survey, #DS21

Thomassen, C.: The genus problem for cubic graphs. J. Comb. Theory Ser. B 69(1), 52–58 (1997)