O'Reilly logo

Topics in Topological Graph Theory by Jonathan L. Gross, Robin J. Wilson, Lowell W. Beineke

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

2Maximum genus

JIANER CHEN and YUANQIU HUANG

1. Introduction

2. Characterizations and complexity

3. Kuratowski-type theorems

4. Upper-embeddability

5. Lower bounds

References

        Since the introductory investigation by Nordhaus, Stewart and White, the maximum genus of a graph has attracted considerable attention from mathematicians and computer scientists. In this survey, we focus on the progress in recent years. In particular, we study its characterizations, algorithmic complexity, upper-embeddability and lower bounds.

1. Introduction

The maximum genus γmax(G) of a graph G is the greatest integer k for which there exists a cellular embedding of G into the orientable surface of genus k. For example, the maximum genus of a tree or a cycle ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required