TY - JOUR
AU - Bose, Prosenjit
AU - De Carufel, Jean-Lou
AU - Shaikhet, Alina
AU - Smid, Michiel
PY - 2017/02/01
Y2 - 2024/06/13
TI - Essential Constraints of Edge-Constrained Proximity Graphs
JF - Journal of Graph Algorithms and Applications
JA - JGAA
VL - 21
IS - 4
SE -
DO - 10.7155/jgaa.00422
UR - https://jgaa.info/index.php/jgaa/article/view/paper422
SP - 389-415
AB - 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 <i>relative neighbourhood graph</i>, <i>Gabriel graph</i>, $\beta$<i>-skeleton</i> and <i>Delaunay triangulation</i>.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.
ER -