Theory and Application of Graphs
==========================================================================
Chapter 3
Plane
Graphs and Planar Graphs
As we have seen, a graph can be represented graphically, that is,
a graph can be drawn in the plane, and it is this kind of graphical presentation that helps us intuitively understand many
of structural properties of graphs. In many real-world problems, for example, layout of printed circuits, one wish to draw a graph
in the plane such that its edges intersect only at their end-vertices, such a graph is called to be planar. A natural and
important question is how to decide whether a given graph is planar or not. We will, in this chapter, discuss and answer this
problem.
First, we will introduce the well-known Euler's formula on a connected plane graph, from which we deduce some of the basic
properties of planar graphs. Then, present a remarkably simple characterization of a planar graph, that is, the well-known
Kuratowski's theorem. With theory of graphic spaces, we introduce the concept of combinatorial dual of a graph, and making use of
Kuratowski's theorem, describe another characterization of a planar graph, that is, Whitney's theorem.
Lastly, as applications of planar graphs, we will show that there are only five regular
polyhedra, which were known by the ancient
Greeks over two thousand years ago; and describe an efficient algorithm for testing the planarity of a given graph and, thus,
for solving the problem of layout of printed circuits.
|
