Outerplanar Graphs

Today, I discuss some topics of graph theory because I want to establish some machinery necessary to start talking about graph colorings (which I will talk about next). For those of you who are unfamiliar with this field of study, the following definitions will help very much.

Definition: A simple graph, $G=(V,E)$ is comprised of a set $V$ of elements called vertices, and a set $E$ of unordered pairs of vertices $v,w \in V$ such that there are no multiple edges between two vertices nor are there edges looping from a vertex to itself.

We can draw $G$ in the plane by denoting its vertices as nodes, and its edges as lines drawn between two nodes if those nodes are connected. See the graph $G=(V,E)$ in the Figure 1.

Definition: A planar graph is a graph $G=(V,E)$ that can be drawn in the plane such that no two edges cross.

Definition: An outerplanar graph is a planar graph such that no vertex is bounded by interior faces of $G$; that is, every vertex lies on the unbounded face of $G$.

Definition: A proper coloring of a graph is a graph in which all of the vertices are colored some color under the condition that no two vertices that share an edge are colored the same color.

Definition: The chromatic number of a graph $G$ is the minimum number of colors $G$ needs in order to be properly colored—denoted as $\chi(G) = n$ where $n$ is the chromatic number of $G$.

Definition: A maximal outerplanar graph $G$ is an outerplanar graph such that the addition of one more edge to $G$ would render it no longer outerplanar.

Definition: A simple polygon graph is a drawing of a regular polygon in the plane, where its vertices are the vertices of our simple polygon graph without the restriction of angles between the edges.

Definition: A triangulation graph of a simple polygon graph is a polygon graph comprised entirely of triangles, or $K_3$’s or 3-cycles depending on how you want to look at it, such that there are no edge crossings.

Now, the theorem that I want to prove today is the following.

Theorem: A graph is a maximal outerplanar graph if and only if it is a triangulation graph of a simple polygon graph.

Proof:[1]

($\Rightarrow$) Let $G$ be a triangulation graph of a simple polygon graph. Clearly, it is a maximal outerplanar graph, for any additional interior edge results in a edge crossing and any additional exterior edge results in bounding a vertex by interior faces.

($\Leftarrow$) Let $G$ be a maximal outerplanar graph. It follows that $G$ satisfies the following conditions.

1. Every exterior edge $e$ has exactly one vertex with edges on both sides of $e$.

2. Every interior edge $e$ has exactly two vertices with edges on both sides of $e$, one on either side of $e$.

3. $G$ has no cutpoints—a vertex, which, upon removal, disconnects $G$.

For (1), suppose that the edge $e$ is on the exterior of the maximal outerplanar graph. Then that means, that any vertices that connect to the end-vertices of $e$ are one one side of $e$–that is to say that the edges connecting the end points of $e$ to other vertices must pass through $G$’s interior. Now, if $e$ had no vertices with edges on both sides of $e$, then $G$ would not be maximal. If $e$ had more than one vertex with edges on both sides of $e$, then either there is an edge crossing, or one vertex is bounded by the interior face of another vertex. Thus, there is exactly one vertex with edges on both sides of $e$. And, we know that this vertex has edges on both sides of $e$ for otherwise, $G$ would not be maximal. For a visual representation of this contradiction, see Figure 10.

For (2), in order for $e$ to be interior, there must be at least one vertex on either side of $e$ that has edges connecting to both end-vertices of $e$. Then, by the same argument as above, there can only be exactly one vertex on either side of $e$ that connects to both sides of $e$.

For (3), suppose $G$ has a cutpoint, the vertex $v$. Then, $G-v$ results in $k$ disconnected components of $G$ labeled $G_1, G_2, \cdots, G_k$, where we label $G_1$ first, and then label the rest of the components in a clockwise fashion. Then, we can connect $G_i$ to $G_{i+1}$ with an edge in such a way that we would not make $v$ an internal edge of $G$. This contradicts that $G$ is maximal, thus no such $v$ exists.

Notice that (1) and (2) illustrate that $G$ is made up of triangles that have been, informally, pasted together. Notice that (3) illustrates that the boundary of $G$ is polygon. Therefore combined, we see that $G$ is a triangulation graph of a simple polygon graph.

[1] I thought of the following proof in a less formal setting and searched to find any literature that structued the proof more formally. Thankfully, Joseph O’Rourke actually published this proof in the exact way I was thinking of it in Art Gallery Theorems and Algorithms using formal terms. As such, much credit of this proof is due to his work cited here: O’Rourke, J. Art Gallery Theorems and Algorithms. Oxford University Press, 1987.