What makes a Tree a Straight Skeleton
Oswin Aichholzer, Howard Cheng, Satyan L. Devadoss, Thomas Hackl, Stefan G. Huber, Brian Li, Andrej Risteski · 2012
Let G be a cycle-free connected straight-line graph with predefined edge lengths and fixed order of incident edges around each vertex. We address the problem of decid-ing whether there exists a simple polygon P such that G is the straight skeleton of P. We show that for given G such a polygon P might not exist, and if it exists it might not be unique. For the later case we give an ex-ample with exponentially many suitable polygons. For small star graphs and caterpillars we show necessary and sufficient conditions for constructing P. Considering only the topology of the tree, that is, ignoring the length of the edges, we show that any tree whose inner vertices have degree at least 3 is isomorphic to the straight skeleton of a suitable convex polygon. 1