Finding a Maximum-Genius Graph Imbedding
- Finding a Maximum-Genius Graph Imbedding
- Furst, Merrick L.
Gross, Jonathan L.
McGeoch, Lyle A.
- Computer Science
- Persistent URL:
- Columbia University Computer Science Technical Reports
- Part Number:
- Department of Computer Science, Columbia University
- Publisher Location:
- New York
- 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.
- Computer science
- Item views
text | xml
- Suggested Citation:
- Merrick L. Furst, Jonathan L. Gross, Lyle A. McGeoch, 1987, Finding a Maximum-Genius Graph Imbedding, Columbia University Academic Commons, https://doi.org/10.7916/D8N87JS8.