I am reading graph theory from the book by Frank Harary.
There the following definitions are given:
Outerplanar Graph: A planar graph that can be embedded in the plane so that all its vertices lie on the same face.
Maximal Outerplanar Graph: An outerplanar graph in which no line can be added without losing outerplanarity.
Then the following statement is written:
"Every maximal outerplane graph is a triangulation of a polygon."
I am facing problem in understanding the above statement.
I will explain my problem with the following diagram:
Here, the graph is an outerplane graph as all the points of the graph lie on the boundary of the interior face. The maximal outerplane graph will be obtained by the triangulation of the interior face, but, this face is not a polygon. Then what does the above statement mean to say by the "triangulation of polygon" ?
When you say
you are referring to something like these (there are several other possibilities, too):
These are not actually outerplanar graphs! There is no longer any face that contains all the vertices. So any statement that begins "Every [...] outerplanar graph is..." does not apply to these graphs. They are not a counterexample.
You may have been hoping that if you start with an outerplanar graph and triangulate it, you will get a maximal outerplanar graph. That is not the definition of a maximal outerplanar graph. The definition of "maximal" is "no more edges can be added while preserving the outerplanar property". Nothing about triangulations! In the diagrams above, we added a few edges too many.
It is true that starting with a polygon and triangulating it is one way to get a maximal outerplanar graph. (The statemen you quoted doesn't say this, though; it says the converse.) Here, since we didn't start with a polygon, there are no promises about what we'll get when we triangulate.