**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:**