Inverse problems

Introduction. The Voronoi diagram1 of points or the straight skeleton2 of a PSLG3 can itself be interpreted as a PSLG (with some infinite edges pointing to a vertex at infinity). Hence, we can ask for any given graph G whether G can be realized as a Voronoi diagram or a straight skeleton. Depending on how much geometric information of G is given we end up with different problems.

Abstract graphs. It has been shown by Dillencourt4 and Dillencourt and Smith5 that every 4-connected planar graph and every outer-planar graph can be realized as the Voronoi diagram of points. In [Aic*12b] we showed that every tree can be realized as the straight skeleton or the Voronoi diagram of a convex polygon. In [Aic*15] we gave sufficient and necessary conditions for a directed tree to be the (directed) straight skeleton of a polygon. (The direction of an edge of the straight skeleton is given by the direction of the wavefront propagation.)

Phylogenetic trees. Cheng et al.6 motivated the question of realizability of phylogenetic trees as the straight skeleton polygons. Here not only the structure of the tree is given but also the lengths of the edges and the incidence orders of the vertices. That is, one is allowed to rotate edges of the trees, as long as the incidence orders and the edge Lent’s are preserved.

Hence, the problem could also be stated as follows: Can we rotate the edges at the inner vertices in a way that the straight skeleton of the polygon that results from cyclically connecting the leaf nodes is identical to the tree? In [Aic*12, Aic*12b] we gave a method that checks whether a (phylogenetic) caterpillar graph7 can be realized. We showed that there can be zero but at most finitely many realizations and we gave a construction scheme for suitable polygons. In the worst case at least an exponential number of realizations may exist, even for caterpillar graphs. For general phylogenetic trees the problem is still open. It is even unclear whether there can be infinitely many realizations for a general phylogenetic tree.

Phylogenetic tree

Geometric graphs. In [BHH*13, BHH*13b] we asked whether a PSLG G can be realized as the straight skeleton of a PSLG H. That is, the locus of each vertex of G is fixed. (In [BHH*13] we considered the special case where G is a tree with the leaf-edges extended to infinity.)

We started with a characterization of straight skeletons, which also allows to implement O(n) a-posteriori validity checks in straight-skeleton implementations. The central vehicle for the recognition problem of straight skeletons as a framework that successively reflects faces of G and suitable supporting lines of edges of potential graphs H along a spanning tree of the dual of G to a designated face of G. This allows us to tackle to problem simultaneously in all cells of G. At the end we can compute a representation of all possible solutions H in O(n log n) time, where n denotes the number of edges of G.

It turns out that the very same technique can also be used to determine all possible point sets whose Voronoi diagram is equal to G in O(n log n) time. Hence, our framework fills a gap in the paper by Ash and Bolker8, which required the assumption that all vertices of G are of odd degree.

In the following figure the red point set, the blue point set, the red polygon and the blue polygon each realize the same Voronoi diagram and straight skeleton, respectively.

Geometric graphs

  1. Voronoi diagram

  2. Straight skeleton

  3. Planar straight-line graph

  4. M. Dillencourt, Realizability of Delaunay Triangulations, Information Processing Letters, 33(6):283-287, 1990. 

  5. M. Dillencourt, W. Smith, Graph-Theoretical Conditions for Inscribability and Delaunay Realizability, Discrete Mathematics, 161(1-3):63-77, 1996. 

  6. H. Cheng, S. Devadoss, B. Li, A. Risteski. Skeletal rigidity of phylogenetic trees, arXiv:1203.5782v1[cs.CG]

  7. Caterpillar graph. If you remove the leaf vertices only a path (the backbone) remains. The phylogenetic tree shown above is a caterpillar graph. 

  8. P. Ash, E. Bolker, Recognizing Dirichlet Tessellations, Geometriae Dedicata, 19:175-206, 1985.