  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, $\beta$-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_\beta(V, S)$ for $1 \leq \beta \leq 2$, where $CG_\beta(V, S)$ is the
constraint $\beta$-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.
