Back to Search
Start Over
A LINEAR TIME ALGORITHM FOR EMBEDDING GRAPHS IN AN ARBITRARY SURFACE.
- Source :
-
SIAM Journal on Discrete Mathematics . 1999, Vol. 12 Issue 1, p6-26. 21p. - Publication Year :
- 1999
-
Abstract
- For an arbitrary fixed surface S, a linear time algorithm is presented that for a given graph G either finds an embedding of G in S or identifies a subgraph of G that is homeomorphic to a minimal forbidden subgraph for embeddability in S. A side result of the proof of the algorithm is that minimal forbidden subgraphs for embeddability in S cannot be arbitrarily large. This yields a constructive proof of the result of Robertson and Seymour that for each closed surface there are only finitely many minimal forbidden subgraphs. The results and methods of this paper can be used to solve more general embedding extension problems. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 12
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 13220183
- Full Text :
- https://doi.org/10.1137/S089548019529248X