A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
Author:
- Bojan MoharBMBojan Mohar
- 1 January 1999
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 12 (1) , 6-26
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.Keywords
This publication has 25 references indexed in Scilit:
- A Kuratowski theorem for nonorientable surfacesJournal of Combinatorial Theory, Series B, 1989
- Finding a maximum-genus graph imbeddingJournal of the ACM, 1988
- A linear algorithm for embedding planar graphs using PQ-treesJournal of Computer and System Sciences, 1985
- A kuratowski theorem for the projective planeJournal of Graph Theory, 1981
- 103 Graphs that are irreducible for the projective planeJournal of Combinatorial Theory, Series B, 1979
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithmsJournal of Computer and System Sciences, 1976
- Efficient Planarity TestingJournal of the ACM, 1974
- Dividing a Graph into Triconnected ComponentsSIAM Journal on Computing, 1973
- Time bounded random access machinesJournal of Computer and System Sciences, 1973
- Additivity of the genus of a graphBulletin of the American Mathematical Society, 1962