Given a tree $T$ with maximum degree three, is there always a simple polygon $P$ such that the dual of every triangulation (without Steiner points) of $P$ is equal to $T$?
Yes. To show this, I will give a procedure to get the seemingly slightly stronger result*:
Given a tree $T$ with maximum degree three, construct a simple polygon $P$, such that the unique triangulation of $P$ (without Steiner points) has $T$ as its dual.
Start by creating an initial triangle $\Delta_0$, representing some vertex $v_0$ in $T$ and add $v_0$ to the queue $Q$.
Then, repeat the following until $Q$ is empty:
- Pop the top element, $v$, from the queue.
- For each neighboring vertex $w$ that for which we have not placed a triangle yet, choose a side $AB$ of triangle $\Delta_v$ and a point $D$ inside the conical regions generated by the line through $AB$ and its neighboring segments, such that the triangle $\Delta ABD$ does not intersect any other triangles. (See figure below) Set $\Delta_w\leftarrow\Delta ABD$ and add $w$ to $Q$.
This image gives an example of a possible polygon $P$ (left) for the given $T$ (right)
To see why this procedure works, first note that after creating a new triangle, the segments $AB$ and $AD$ generate a cone that has a non-empty region not-intersecting with the existing triangles (see also the earlier figure), so we can find a suitable point at every step and create a polygon.
Second, we have chosen the triangles such that line segment between $CD$ does not completely lie inside $P$. If there exists a corner-point $Q \notin \{B,D\}$ of the already placed triangles such that $DQ$ is fully in $P$, then it must lie inside the cones generated by $AD$ and $BD$. However, since the part of this cone that does not lie inside $\Delta ABD$ is contained in the cone generated by the earlier placed triangle, such a $Q$ exists only if there exists an analogous point for the earlier placed triangle. Since there does not exist such a point for the first triangle, this means there is no such point for any triangle we add.
This means that all pairs $(X,Y)$ of any corner point of $P$ for which the segment $XY$ is fully contained in $P$ is already in the constructed triangulation, so the triangulation is unique for $P$ (all triangulations add the same number of internal segments)
Note that the polygons constructed in this method tend to have rather sharp angles. I suspect arbitrary large graphs require polygons with arbitrary small angles, which could be a problem when drawing these polygons with finite precision.
*: The difference is that, if we interpret 'unique' as up to isomorphism (which is consistent with uniqueness of triangulations and duals being different), we would be ok with a polygon having multiple triangulations that all have isomorphic duals. However, it is possible to 'attach' more triangles to those polygons to ensure some duals are no longer isomorphic.
