Essential Constraints of Edge-Constrained Proximity Graphs

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 logn)-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. Submitted: October 2016 Reviewed: December 2016 Revised: January 2017 Accepted: January 2017 Final: January 2017 Published: February 2017 Article type: Regular paper Communicated by: G. Liotta This work was partially supported by NSERC. E-mail addresses: jit@scs.carleton.ca (Prosenjit Bose) jdecaruf@uottawa.ca (Jean-Lou De Carufel) alina.shaikhet@carleton.ca (Alina Shaikhet) michiel@scs.carleton.ca (Michiel Smid) 390 Bose, De Carufel, Shaikhet, Smid Edge-Constrained Proximity Graphs