Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00422
Essential Constraints of EdgeConstrained Proximity Graphs
Vol. 21, no. 4, pp. 389415, 2017. Regular paper.
Abstract Given a plane forest $F = (V, E)$ of $V = n$ points, we find the minimum set $S \subseteq E$ of edges such that the edgeconstrained 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.

Submitted: October 2016.
Reviewed: December 2016.
Revised: January 2017.
Final: January 2017.
Accepted: January 2017.
Published: February 2017.
Communicated by
Giuseppe Liotta
