Geometric Structures: Session V

Plane Graphs

Prepared by:

Joseph Malkevitch
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk

Education relies heavily on books, blackboards, and computer screens. So drawing graphs on a flat surface in a clear way is very valuable. A plane graph is one which has been drawn in the plane so that edges meet only at vertices. An example is shown in Figure 1.



Figure 1


A planar graph is one which is isomorphic to a plane graph. It is easy to see the vertices and edges in a plane graph but there is another feature of interest in plane graphs - the faces. These are the regions that have no edges in the interior, with the exception of the one special region, usually called the infinite face, which surrounds all the faces. Thus, all the faces of a plane graph except for the special infinite face are bounded. (A set X in the plane is bounded if it can be enclosed in a Euclidean circle with a finite radius.) In Figure 1 there are seven faces and the infinite face is bounded by the circuit 1, 2, 3, 4, 5, 6, 1. The number of sides of a face is the number of edges in the circuit that forms the boundary of the face. In Figure 1 there are faces with 3, 4, 5, and 6 sides. An example of a 3-sided face, or 3-gon is: 2, 10, 3, 2 while 9, 5, 4, 11, 9 is a 4-gon. Self-loops give rise to 1-sided faces, while multiple edges often give rise to 2-sided faces. Figure 2 has three faces: two 4-gons including the infinite face and one 2-gon or digon.



Figure 2


Figure 3 has a pair of vertices joined by two edges but it has no two-sided face. The infinite face in this graph is a 5-gon, while all the other faces are 3-gons.


Figure 3


Figure 1 shows a plane graph which is 3-valent except for one vertex while Figure 4 shows a 4-valent plane graph. Plane graphs which have the same valence at every vertex can either be 1-valent, 2-valent, 3-valent, 4-valent or 5-valent, but cannot be k-valent for k more than 5.



Figure 4

Do Now 1:

Draw diagrams of connected 1-valent, 2-valent, 3-valent, 4-valent, and 5-valent graphs.

Usually, due to the Jordan Curve Theorem, when one moves from one "side" of an edge to the other in a plane graph, one moves from one face to another. Thus, usually edges are part of the boundary of exactly two faces. However, sometimes an edge has the same face on both "sides" of the edge. Edges of this kind which appear in Figure 5 are 10, 11 and 10, 12 and 2, 10.



Figure 5


If we let pk denote the number of faces in a plane graph with k sides, then for the graph in Figure 3 we have: p3 = 3 and p5 = 1. If we add up all of the sides that occur in the different faces we get 3(3) + 5 = 14, which is twice the number of edges in Figure 3. The graph in Figure 3 has 7 edges. When each bounds two faces we have a general theorem here: the sum of the number of edges in the faces of a plane graph is twice the total number of edges in the graph. To make this theorem true for graphs such as those in Figure 5, where some of the edges are part of the boundary of only one face, we need to count such edges twice. (This is the analogue of our decision to count self-loops twice when we looked at the valence of a vertex.) The infinite face in Figure 5 has 11 sides. Hence, we have p3 = 2, p4 = 4, p5 =1 and p11 = 1. Thus, twice the number of edges in the graph in Figure 5 is 3(2) + 4(4) + 5(1) + 11(1) = 38. You can check that Figure 5 does indeed have 19 edges.

An important subtlety here is that while two graphs drawn in the plane may be isomorphic, they can have different values for pk.

You can verify for yourself that the graph in Figure 6 is isomorphic to that in Figure 3.


Figure 6


However, while there is no 2-gon in the drawing of Figure 3 there is a 2-gon in Figure 6. There are isomorphic plane graphs without multiple edges which determine "face vectors."

Do Now 2:

Draw a pair of plane connected graphs which are isomorphic but for which the number of sides of the faces for these isomorphic graphs is different.

It turns out there is a relatively simple condition which guarantees that the number of sides of faces that are determined by plane graphs for different drawings of the same graph cannot vary.

Theorem (Hassler Whitney (1907-1989))

If G is a planar 3-connected graph, then the face vector (p3, p4, ..., pn) is the same for all embeddings of G in the plane.

Definition: A graph G is 3-connected if for any pair of vertices u and v in G, there are at least 3 different paths from u to v that have only the vertices u and v in common.

Figure 1 and Figure 4 are both examples of 3-connected graphs. One can have different visual appearance for 3-connected graphs because the number of sides of the infinite face can vary from one drawing of the graph to another. However, despite the different appearance of the two drawings, the two graphs shown in Figure 7 have the same face vector. Thus, for one of the drawings in Figure 7 the infinite face is a 3-gon, while for the other it is a 4-gon.


Figure 7

It turns out that the planar 3-connected graphs are those that can arise as the vertex edge graphs of convex 3-dimensional polyhedra. This is the theorem of Steinitz as rephrased in graph theory terms by Branko Grünbaum and Theodore Motzkin.

Theorem (Ernest Steinitz)

A graph G is the edge-vertex graph of a convex 3-dimensional polyhedron if and only if G is planar and 3-connected.

The other key result about 3-dimensional polyhedra is Euler's Polyhedral Formula. In a slightly more general form for graphs it states: If G is a plane graph with V vertices, E edges and F faces then:

V + F - E = 2


In this form the result goes back to Cauchy.