The Complexity of the Graph Embedding Problem
Dan Archdeacon · 1990
We investigate the computational complexity of determining if a graph G on v vertices embeds in a surface S. Robertson and Seymour have given an O(v 3) decision algorithm for this embedding problem. We show here how the use the yes/no output from their algorithm to construct the embedding, that is, we self-reduce the search algorithm to the decision algorithm. We conclude that for each fixed surface S there exists an O(v 10) algorithm for constructing an embedding or answering that no embedding exists.