This question came up in an undergraduate math club meeting yesterday.

As we know, a graph is planar if it can be embedded in the plane with no edges crossing. A famous necessary and sufficient combinatorial condition for a graph to be planar is Kuratowski's theorem: a graph $G$ is planar iff it does not contain a subdivision of the complete graph $K_5$ or the complete bipartite graph $K_{3,3}$.

Now consider a polygon $P$ in the plane (a finite sequence of vertices successively joined by non-crossing line segments). I do not require that $P$ be convex. A triangulation of $P$ consists of the original polygon $P$ together with additional non-crossing line segments joining vertices of $P$, such that the interior of $P$ is partitioned into triangles. (So you are not allowed to add internal vertices. I am not sure if this is exactly the usual definition of "triangulation".) You can view this triangulation as a graph, using the vertices of the original polygon, and all the original and added line segments as edges.

Here is a crude drawing. The green points are the vertices, the black lines are the original polygon, the red lines are the added segments of the triangulation.

enter image description here

Let me say an (abstract) finite graph $G$ is a polygon triangulation if there exists a polygon $P$ and a triangulation of $P$ which, as a graph, is isomorphic to $G$.

Given a finite graph $G$, is there a necessary and sufficient combinatorial condition for $G$ to be a polygon triangulation? (Perhaps analogous to Kuratowski?)

We came up with some necessary conditions:

  • $G$ must be planar, obviously. So by Kuratowski it may not contain a subdivision of $K_5$ or $K_{3,3}$.

  • $G$ must be connected, also obvious.

  • $G$ must be 3-colorable. (So not every planar graph is a polygon triangulation; in particular, $K_4$ is not a polygon triangulation.) This much seems to be well known.

(Here is a sketch of a proof for 3-colorability. Induct on the number $n$ of vertices of $G$. The base case $n=3$ is trivial. For the inductive step, let $G$ be a polygon triangulation with $n$ vertices. Fix an embedding of $G$ which is a polygon triangulation. Consider the dual graph $G'$ of $G$, excluding the outside face. $G'$ must be acyclic, because a cycle in $G'$ would make a loop inside $P$ that encloses a vertex of $P$, contradicting the simply-connectedness of $P$. So $G'$ contains a leaf; this corresponds to a triangular face of $G$ with two exterior edges $e_1, e_2$. Let $v$ be the vertex between those edges; it cannot be incident on any other edges, so $v$ has degree 2. By the inductive hypothesis we can properly 3-color $G -v$. But since $v$ has degree 2 we can color $v$ also, so $G$ is 3-colorable.)

But we didn't discover a necessary and sufficient condition.

(Note: This is not my field so it's very likely that I'm misusing terminology or ignorant of well-known facts. Please feel free to enlighten me!)

  • $\begingroup$ Is it enough to add a condition on the number of edges? $\endgroup$ – Michael Burr Mar 11 '15 at 16:13
  • $\begingroup$ It is likely easier (probably a lot easier because the Euler characteristic applies) to determine when a graph is a total (interior and exterior) triangulation of a polygon. $\endgroup$ – Michael Burr Mar 11 '15 at 16:20
  • 1
    $\begingroup$ You might also need a condition that the intersections of the neighbor sets of two vertices connected by an edge has a third vertex in common. $\endgroup$ – Michael Burr Mar 11 '15 at 16:27
  • 1
    $\begingroup$ @Casteels: I don't think so, because $K_4$ is maximal planar (trivially), but not a polygon triangulation in my sense. One of the vertices has to go in the middle of the polygon, which I don't allow. $\endgroup$ – Nate Eldredge Mar 11 '15 at 16:34
  • 1
    $\begingroup$ @Casteels It is not the same as a maximal planar graph because the outer face need not be a triangle. $\endgroup$ – Michael Burr Mar 11 '15 at 16:34

The standard name for the graphs you describe are maximal outerplanar graphs.

As noted on the linked-to Wikipedia page, a graph is outerplanar if and only if it has no $K_4$ or $K_{2,3}$ minor, and an outerplanar graph is maximal if and only if it has $2n-3$ edges, where $n$ is the number of vertices.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.