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

Publication
, Conference

Filotti, IS; Miller, GL; Reif, J

Published in: Proceedings of the Annual ACM Symposium on Theory of Computing

April 30, 1979

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.

### Duke Scholars

##### Altmetric Attention Stats

##### Dimensions Citation Stats

## Published In

Proceedings of the Annual ACM Symposium on Theory of Computing

## DOI

## ISSN

0737-8017

## Publication Date

April 30, 1979

## Start / End Page

27 / 37

### Citation

APA

Chicago

ICMJE

MLA

NLM

Filotti, I. S., Miller, G. L., & Reif, J. (1979). On determining the genus of a graph in 0(V

^{0}(^{g})) steps. In*Proceedings of the Annual ACM Symposium on Theory of Computing*(pp. 27–37). https://doi.org/10.1145/800135.804395Filotti, I. S., G. L. Miller, and J. Reif. “On determining the genus of a graph in 0(V

^{0}(^{g})) steps.” In*Proceedings of the Annual ACM Symposium on Theory of Computing*, 27–37, 1979. https://doi.org/10.1145/800135.804395.Filotti IS, Miller GL, Reif J. On determining the genus of a graph in 0(V

^{0}(^{g})) steps. In: Proceedings of the Annual ACM Symposium on Theory of Computing. 1979. p. 27–37.Filotti, I. S., et al. “On determining the genus of a graph in 0(V

^{0}(^{g})) steps.”*Proceedings of the Annual ACM Symposium on Theory of Computing*, 1979, pp. 27–37.*Scopus*, doi:10.1145/800135.804395.Filotti IS, Miller GL, Reif J. On determining the genus of a graph in 0(V

^{0}(^{g})) steps. Proceedings of the Annual ACM Symposium on Theory of Computing. 1979. p. 27–37.## Published In

Proceedings of the Annual ACM Symposium on Theory of Computing

## DOI

## ISSN

0737-8017

## Publication Date

April 30, 1979

## Start / End Page

27 / 37