Block Additivity of ℤ2-Embeddings

Schaefer, Marcus and Štefankovič, Daniel (2013) Block Additivity of ℤ2-Embeddings. In: 21st International Symposium, GD 2013, September 23-25, 2013, Bordeaux, France , pp. 185-195 (Official URL:

Full text not available from this repository.


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.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.490 Embeddings
Z Theory > Z.750 Topology
ID Code:1374

Repository Staff Only: item control page


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)