Theorem (B.M. 1999) For every surface S there is a linear time algorithm which, for a given graph G, either finds an embedding of G in S or returns a subgraph of G that is a subdivision of a Kuratowski graph for S.
This result appeared in
[1] B. Mohar, A linear time algorithm for embedding graphs in an arbitrary
surface, SIAM J. Discrete Math. 12 (1999) 6-26.
(Cf. also B. Mohar, Embedding graphs in an arbitrary surface in linear time,
Proc. 28th Ann. ACM STOC, Philadelphia,
ACM Press, 1996, pp. 392-397.)
PDF file
It relies on three other papers
[2] B. Mohar,
Universal obstructions for embedding extension problems
(Download PDF file)
[3] M. Juvan, B. Mohar,
Extending 2-restricted partial embeddings of graphs
(Download PDF file)
[4] M. Juvan, J. Marinček, B. Mohar,
Obstructions for simple embeddings
(Download PDF file)
and partially also on three further ones:
[5] M. Juvan, J. Marinček, B. Mohar,
Elimination of local bridges,
Math. Slovaca 47 (1997) 85-92.
(PDF file)
[6] B. Mohar,
Obstructions for the disk and the cylinder embedding extension problems,
Combin. Probab. Comput. 3 (1994) 375-406.
(PDF file)
[7] M. Juvan, B. Mohar,
Obstructions for 2-Möbius band embedding extension problem,
SIAM J. Discrete Math. 10 (1997) 57-72.
(PDF file)
A linear time implementation of the algorithm for the projective plane described in
[8] B. Mohar, Projective planarity in linear time, J. Algorithms 15 (1993) 482-502
is not too hard (but neither easy). However, already the linear time torus
algorithm contains all the main difficulties from [4].
A result of Fiedler, Huneke, Richter, and Robertson gives rise to a
simplified torus algorithm:
[9] M. Juvan and B. Mohar, A simplified algorithm for embedding a graph into the torus. (Download PDF file)
If one does not insist on linearity, this algorithm can be further simplified. Recently, it has been implemented by Alen Orbanić. The implementation is made in C++ by using data structures and basic algorithms from the LEDA package, with the intention to be made part of LEDA project (as a LEDA Extension Package). It is to be mentioned that the whole program has about 10000 lines of C++ code and that it is thoroughly tested at this time. Anyone wishing to obtain a copy of the program (to be used exclusively for academic purposes) should contact Alen Orbanić by email at
Some related WEB pages: