1987 Reports

Finding a Maximum-Genius Graph Imbedding

Furst, Merrick L.; Gross, Jonathan L.; McGeoch, Lyle A.

The computational complexity of constructing the imbeddings of a given graph into surfaces of different genus is not well-understood. In this paper, topological methods and a reduction to linear matroid parity are used to develop a polynomial-time algorithm to find a maximum-genus cellular imbedding. This seems to be the first imbedding algorithm for which the running time is not exponential in the genus of the imbedding surface.