Abstract
We study embeddings of graphs in surfaces up to ℤ2-homology. We introduce a notion of genus mod 2 and show that some basic results, most noteworthy block additivity, hold for ℤ2-genus. This has consequences for (potential) Hanani-Tutte theorems on arbitrary surfaces.
Chapter PDF
Similar content being viewed by others
References
Sarkaria, K.S.: A one-dimensional Whitney trick and Kuratowski’s graph planarity criterion. Israel J. Math. 73(1), 79–89 (1991)
Chojnacki (Haim Hanani), C.: Über wesentlich unplättbare Kurven im drei-dimensionalen Raume. Fundamenta Mathematicae 23, 135–142 (1934)
Pelsmajer, M.J., Schaefer, M., Stasi, D.: Strong Hanani–Tutte on the projective plane. SIAM Journal on Discrete Mathematics 23(3), 1317–1323 (2009)
Mohar, B., Thomassen, C.: Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (2001)
Levow, R.B.: On Tutte’s algebraic approach to the theory of crossing numbers. In: Hoffman, F., Levow, R.B., Thomas, R.S.D. (eds.) Proceedings of the Third Southeastern Conference on Combinatorics, Graph Theory and Computing, Boca Raton, Fla., Florida Atlantic University, pp. 315–314 (1972)
Stillwell, J.: Classical topology and combinatorial group theory. Second edn, 2nd edn. Graduate Texts in Mathematics, vol. 72. Springer, New York (1993)
de Longueville, M.: A course in topological combinatorics. In: Universitext, Springer, New York (2013)
Babai, L., Frankl, P.: Linear algebra methods in combinatorics with applications to geometry and computer science. Department of Computer Science, The University of Chicago (1992)
Thomassen, C.: The graph genus problem is NP-complete. J. Algorithms 10(4), 568–576 (1989)
Mohar, B.: A linear time algorithm for embedding graphs in an arbitrary surface. SIAM J. Discrete Math. 12(1), 6–26 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Schaefer, M., Štefankovič, D. (2013). Block Additivity of ℤ2-Embeddings. In: Wismath, S., Wolff, A. (eds) Graph Drawing. GD 2013. Lecture Notes in Computer Science, vol 8242. Springer, Cham. https://doi.org/10.1007/978-3-319-03841-4_17
Download citation
DOI: https://doi.org/10.1007/978-3-319-03841-4_17
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03840-7
Online ISBN: 978-3-319-03841-4
eBook Packages: Computer ScienceComputer Science (R0)