Neighbourhood　relational　graphs　are　widely　used　in　Geosciences.　Given　a　set　of　spatial　objects　(vertices)　in　the　plane　together　with　a　set　of　spatial　obstacles　and　spatial　facilitators　in　straight-line　edges,　the　constrained　Delaunay　graph　(CD-graph)　is　an　undirected　graph　representing　the　spatial　adjacency　and　neighbourhood　relation　of　objects.　CD-graph　is　an　approximated　triangulation　of　vertices　with　the　following　properties:　(1)　the　obstacles　are　included　in　the　graph　as　some　barrier　edges　that　block　the　connection　of　the　objects　on　both　sides　of　the　obstacles,　and　the　facilitators　are　included　in　the　graph　as　some　nontrivial　edges　that　connect　the　objects　that　are　broken　by　the　obstacles;　(2)　it　is　as　close　as　possible　to　the　Delaunay　triangulation　(D-TIN).　CD-graph　can　be　used　to　represent　the　spatial　adjacency　and　neighbourhood　relation　of　objects　with　constraints.　A　theoretical　contrast　is　conducted　to　differentiate　CD-graph,　arbitrary　(unconstrained)　D-TIN　and　constrained　D-TIN.　Meanwhile,　a　two-step　constraint-embedding　algorithm　is　proposed　to　build　CD-graph　in　optimal　O(n　log　n)　time　by　using　divide-and-conquer　technique.　Subsequently,　the　Voronoi　diagram　and　D-TIN-based　k-order　neighbours　is　extended　in　CD-graph　to　express　different　scales　of　spatial　adjacency　and　neighbourhood　relation　of　objects.　CD-graph　can　be　widely　used　in　geographical　applications,　such　as　spatial　interpolation,　spatial　clustering　and　spatial　decision　support.