Technical reports:
Finding a Maximum-Genius Graph Impeding
Merrick L. Furst; Jonathan L. Gross; Lyle A. McGeoch
Downloads:
- Title:
- Finding a Maximum-Genius Graph Impeding
- Author(s):
-
Furst, Merrick L.
Gross, Jonathan L.
McGeoch, Lyle A. - Date:
- 1987
- Type:
- Technical reports
- Department:
- Computer Science
- Permanent URL:
- http://hdl.handle.net/10022/AC:P:11837
- Series:
- Columbia University Computer Science Technical Reports
- Part Number:
- CUCS-263-87
- Publisher:
- Department of Computer Science, Columbia University
- Publisher Location:
- New York
- Abstract:
- 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.
- Subject(s):
- Computer science
- Item views:
- 132