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 \subseteq 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\subseteq E$ of edges of a given plane graph $I=(V,E)$ such that $I \subseteq 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.