I have read that; if a polygon contains a hole in it, then the dual graph of a triangulation of the polygon not have to be a tree. But could not get it exactly. How is it possible, what is the relation with the hole in it? If anyone could explain it with a polygon contains hole. I would be very happy and thanks in advance.
3
-
$\begingroup$ See what happens with the subdivision of the figure when you merge some adjacent triangles (and latter polygons) of the subdivision. See what this does to the dual graph. It chooses an edge and collapses it, and the vertices that it joins, to a single vertex. Merging polygons of the subdivision eventually gets you to having the given figure not partitioned. Correspondingly, the dual graph turns into a single vertex with possibly some loops. The dual graph was a tree if and only if there were no loops. You could choose to collapse the edges of a spanning tree, for example. $\endgroup$– plopDec 5, 2020 at 15:29
-
$\begingroup$ To finish it, note that at any stage, the given figure can be (continuously) contracted to the current dual graph of the current subdivision. Therefore their fundamental groups are the same. The fundamental group of a connected region in the plane is zero if and only if it has no holes. This could actually be the formal definition of "not having holes". The fundamental group of a vertex with a few loops is zero if an only if there are no loops. $\endgroup$– plopDec 5, 2020 at 15:31
-
$\begingroup$ Thank you for your comment $\endgroup$– AlemhaDec 5, 2020 at 16:42
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Below is an example of a polygon with a single hole. The red area is the interior of the polygon, and the white triangle in the center is the hole (which lies outside the polygon). In the figure, I've also drawn a triangulation of this polygon. The dual of this triangulation is a cycle with $6$ vertices, and this is not a tree.
However, is this thing I've drawn here really a polygon? That depends on which definition of "polygon" you use. A polygon is often defined as an area bounded by a single polygonal chain that does not intersect itself. This type of polygon is also known as a simple polygon. Sometimes, we want to talk about generalizations of this simple polygon. A polygon with holes is a connected area bounded by several polygonal chains that do not intersect themselves or with each-other.
So, for this answer, I will define a polygon to be either a simple polygon or a polygon with holes. This means that above, I've shown an example of a polygon with a triangulation of which the dual graph is not a tree. This particular polygon is actually an example of something that holds more generally: the dual of a triangulation of a polygon is a tree if and only if the polygon is simple. (Proof idea: since a polygon is connected, the dual graph of the triangulation is also connected. Observe that the boundary of the polygon is disconnected if and only if the dual graph of the triangulation contains a cycle. Since a tree is defined as a connected acyclic graph, the claim follows.)
answered Dec 5, 2020 at 15:05