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

4Algorithms and obstructions for embeddings

BOJAN MOHAR

1. Introduction

2. Planarity

3. Outerplanarity and face covers

4. Disc embeddings and the 2-path problem

5. Graph minors and obstructions

6. The algorithms for embeddability in general surfaces

7. Computing the genus

References

        This chapter gives a brief introduction to algorithms for finding embeddings of graphs in surfaces and discusses obstructions that prevent a graph from having an embedding. It starts with questions related to planarity and continues with obstructions to outerplanar graphs and the 2-path problem. Algorithms and obstructions for embeddings of graphs in surfaces of higher genus are more complicated, and known results are surveyed.

1. Introduction

In this chapter ...

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