zbMATH — the first resource for mathematics

A linear time algorithm for embedding graphs in an arbitrary surface. (English) Zbl 0931.05025
Author’s abstract: 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 subgraph of \(G\) that is homeomorphic to a minimal forbidden subgraph for embeddability in \(S\). A side result of the proof of the algorithm is that minimal forbidden subgraphs for embeddability in \(S\) cannot be arbitrarily large. This yields a constructive proof of the result of Robertson and Seymour that for each closed surface there are only finitely many forbidden subgraphs. The results and methods of this paper can be used to solve more general embedding extension problems.

05C10 Planar graphs; geometric and topological aspects of graph theory
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI