Outer faces in disconnected planar graph

graph theoryplanar-graphs

Consider a planar graph consisting of two components. Assume that each component is a triangle.

We have two faces that are to the left of the edges in each cycle if we consider traversing the cycle in counterclockwise order. Now if the graph was not disconnected and consisted of only a single component that is a cycle I would say that there is an "outer" face as well.

However, what is the correct way to count faces in the case where it is disconnected as we assume? Does each component have an outer face and hence there is a total of 4 faces? If so how can you distinguish the 2 outer faces as are defined on the same area?

Best Answer

We define faces of a plane graph $G$ to be the connected regions of $\mathbb R^2 - G$.

*-----*  *-----*
 \   /    \   /
  \ /      \ /
   *        *

By this definition, the graph above has $3$ faces:

  • Two "normal" faces of length $3$, whose boundaries are $3$-cycles;
  • One "weird" face of length $6$ whose boundary consists of two $3$-cycles.

The "weird" face is not necessarily the unbounded face; if we draw one triangle inside the other, then the region between the two triangles is the "weird" face. Here is what this looks like:

*---------*  
 \ *---* /
  \ \ / /
   \ * /
    \ /
     *

In general, though we'd like the boundary of a face to be a cycle in the graph, this can fail in two ways:

  • When the graph is not connected, the boundary of a face can have multiple pieces, as we see here.
  • Each piece may be a closed walk, not necessarily a cycle, when the graph has bridges.

Note, however, that Euler's formula $$ (\text{# vertices}) - (\text{# edges}) + (\text{# faces}) = 2 $$ only applies to connected graphs! For the $6$-vertex example we're looking at, it would tell us that there are $2$ faces, which is nonsense. The general rule is that $$ (\text{# vertices}) - (\text{# edges}) + (\text{# faces}) = (\text{# components}) + 1. $$

Related Question