2
$\begingroup$

I study Polygon Triangulation and have an execise.

Prove or disprove: The dual graph of the triangulation of a monotone polygon is always a chain, that is, any node in this graph has degree at most two.

It seems like the assumption that the dual graph of the triangulation of a monotone polygon is always a chain is false. But how to prove this.

Let's say if it was true, at least one edge of every triangle would be a part of the boundary of the polygon.

I don't have any idea how approach the proof. Please help me out.

Thanks!

2 Answers 2

4

Does the following serve as a contradiction to the claim? I think a more interesting question would be to prove or disprove that for all monotone polygons there exists a triangulation such that its dual graph is a chain. I'm afraid I do not have anything non-trivial to say about this question. Contradiction for assertion

  • 5
    Well I dont see how showing a producing counterexample is not sufficiently rigorous.2012-04-14
0

It is possible to draw a simple y-monotone polygon that has a triangulation which gives a dual that is not a chain. Consider a polygon that looks like a pointy cross. Triangulate it so that each prong is its own triangle. Then there are two vertices that have 3 neighbors.

http://web.eecs.utk.edu/~booth/494-02/homeworks/hw2sol.html third question . pointy cross triangulation will give two vertices with degree 3 - http://www.wikiwand.com/hu/Ny%C3%ADlv%C3%A9g%C5%B1_kereszt