A linear time algorithm for embedding graphs in an arbitrary surface

For an arbitrary fixed surface S, a linear time algorithm is presented that for a given graph G either finds an embedding of G in S or identifies a su bgraph of G that is homeomorphic to a minimal forbidden subgraph for embedd ability in S. A side result of the proof of the algorithm is that minimal f orbidden subgraphs for embeddability in S cannot be arbitrarily large. This yields a constructive proof of the result of Robertson and Seymour that fo r each closed surface there are only finitely many minimal forbidden subgra phs. The results and methods of this paper can be used to solve more genera l embedding extension problems.