Geodesic
Essential Constraints of Edge-Constrained Proximity Graphs
Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 4, pp. 389-415.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00422
Keywords: proximity graphs, constraints, visibility, MST, Delaunay, beta-skeleton 
@article{JGAA_2017_21_4_a0,
     author = {Prosenjit Bose and Jean-Lou De Carufel and Alina Shaikhet and Michiel Smid},
     title = {Essential {Constraints} of {Edge-Constrained} {Proximity} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {389--415},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2017},
     doi = {10.7155/jgaa.00422},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00422/}
}
TY  - JOUR
AU  - Prosenjit Bose
AU  - Jean-Lou De Carufel
AU  - Alina Shaikhet
AU  - Michiel Smid
TI  - Essential Constraints of Edge-Constrained Proximity Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2017
SP  - 389
EP  - 415
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00422/
DO  - 10.7155/jgaa.00422
LA  - en
ID  - JGAA_2017_21_4_a0
ER  - 
%0 Journal Article
%A Prosenjit Bose
%A Jean-Lou De Carufel
%A Alina Shaikhet
%A Michiel Smid
%T Essential Constraints of Edge-Constrained Proximity Graphs
%J Journal of Graph Algorithms and Applications
%D 2017
%P 389-415
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00422/
%R 10.7155/jgaa.00422
%G en
%F JGAA_2017_21_4_a0
Prosenjit Bose; Jean-Lou De Carufel; Alina Shaikhet; Michiel Smid. Essential Constraints of Edge-Constrained Proximity Graphs. Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 4, pp. 389-415. doi : 10.7155/jgaa.00422. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00422/

Cité par Sources :