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.
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!)
Best Answer
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.