Given a plane forest F = (V, E) of |V | = n points, we find the minimum set S ⊆ E of edges such that the edge-constrained minimum spanning tree over the set V of vertices and the set S of constraints contains F . We present an O(n log n)-time algorithm that solves this problem. We generalize this to other proximity graphs in the constraint setting, such as the relative neighbourhood graph, Gabriel graph, β-skeleton and Delaunay triangulation. We present an algorithm that identifies the minimum set S ⊆ E of edges of a given plane graph I = (V, E) such that I ⊆ CGβ (V, S) for 1 ≤ β ≤ 2, where CGβ (V, S) is the constraint β-skeleton over the set V of vertices and the set S of constraints. The running time of our algorithm is O(n), provided that the constrained Delaunay triangulation of I is given.

Additional Metadata
Persistent URL dx.doi.org/10.7155/jgaa.00422
Journal Journal of Graph Algorithms and Applications
Citation
Bose, P, De Carufel, J.-L. (Jean-Lou), Shaikhet, A. (Alina), & Smid, M. (2017). Essential constraints of edge-constrained proximity graphs. Journal of Graph Algorithms and Applications, 21(4), 389–415. doi:10.7155/jgaa.00422