max planarity and triangulation

1.4k Views Asked by At

Surely this result stated in my course is false.

A plane graph of more then $3$ vertices is maximaly plane iff it is a triangulation

Left to right is clear. Indeed, if one of my interior faces is not a triangle, then I can connect at least two vertices with edges in the interior of my face.

However the other way is not correct. cfr drawing

a) a triangulation which is not maximal since b) is still planar

a) a triangulation which is not maximal since b) is still planar

3

There are 3 best solutions below

2
On

A planar graph $G$ is said to be triangulated (also called maximal planar) if the addition of any edge to $G$ results in a nonplanar graph.

Considering this definition, your graph in $a)$ is not a triangulation at all since you can add an edge to it to get a planar $b)$. The graph in part $b)$ is also not a triangulation, indeed you can add one more edge to it without breaking planarity.

When you have an if and only if statement, this means you can use one of the sides of the statement to define another (in this example, triangulation can be defined as maximal planarity and vice versa). So if $G$ is maximal planar i.e. you can't add an edge without breaking planarity, then it is also called triangulation. However, triangulation is not the same thing as a graph all of whose faces are triangle but it is as same as maximal planarity. Long story short, your graph in $a)$ is not a triangulation.

1
On

I think i need to know your definitions of the terms 'maximaly plane' and 'triangulation'. I understand triangulation as a 'chordal graph': all cycles of four or more vertices have a chord.

This applies to both your graphs. But you can add at least three edges to (a) and two edges to (b) without losing planarity. Hence, they are beautiful couterexamples to prove that triangulation does NOT entail maximal planarity, just like you stated in your question.

(if and only if you agree with my definitions)

0
On

the first drawing is only a weak triangulation, the outer face (or unbounded face) is still a face and has to be triangular, and it isnt in your picture. that also what is causing you issue in the second drawing which isn't even a weak triangulation anymore.