We investigate how neighborhood graphs (such as MST, Relative Neighborhood graph, Gabriel graph, Beta-skeleton and Delaunay triangulation) behave in constraint setting.

Given a set $V$ of $n$ points in the plane and a set of constraints - a plane graph $I = (V,E)$. Each pair of points $u,v \in V$ is associated with a neighborhood defined by some property $P(u,v)$. An edge-constrained neighborhood graph $G (I)$ defined by the property $P$ is a graph with a set of vertices $V$ and a set of edges $E'$ such that $uv \in E'$ if and only if $uv \in E$ or $uv$ has property $P(u,v)$. We are interested in the minimum set of edges $S ⊆ E$ such that $I ⊆ G(V,S)$.