Home

Finding a Maximum-Genius Graph Impeding

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

Title:
Finding a Maximum-Genius Graph Impeding
Author(s):
Furst, Merrick L.
Gross, Jonathan L.
McGeoch, Lyle A.
Date:
Type:
Technical reports
Department:
Computer Science
Permanent URL:
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:
163
Metadata:
View

In Partnership with the Center for Digital Research and Scholarship at Columbia University Libraries/Information Services.