#
On determining the genus of a graph in 0(V ^{0}
( ^{g}
)) steps

Published

Conference Paper

© 1979 Association for Computing Machinery. All rights reserved. Putting all the procedures together we can obtain our genus algorithm. Procedure. Embedding (G,g) (1) Generate Basic Subgraph (G,g), say Lj. (2) Remove Internal Edges (G,L,I). (3) Partition (G,L,I). (4) Quasiplanar (G,L,I). (5) 2-CNF (G,L,I). We can now analyze the running time of Embedding. We list the multiplicative factors for each of the steps (1) to (4): (1) 0((eg).e2g) (2) and (3) 0(e188g) (4) 0((56g)336g). Note that each of these terms is bounded by (g-v)0^. We state this as a theorem: Theorem 1. There exists an algorithm to determine the genus of graph which runs in (g-v)0(g) time. By running Embedding on inputs for successively larger g we can determine the genus of a graph.

### Full Text

### Duke Authors

### Cited Authors

- Filotti, IS; Miller, GL; Reif, J

### Published Date

- April 30, 1979

### Published In

### Start / End Page

- 27 - 37

### International Standard Serial Number (ISSN)

- 0737-8017

### Digital Object Identifier (DOI)

- 10.1145/800135.804395

### Citation Source

- Scopus