Essential Constraints of Edge-Constrained Proximity Graphs - Bose, Prosenjit; De Carufel, Jean-Lou; Shaikhet, Alina; Smid, Michiel (Journal of Graph Algorithms and Applications, 2017)
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 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 SE 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.