Enumerating edge-constrained triangulations and edge-constrainednon-crossing geometric spanning trees

摘要

In this paper, we present algorithms for enumerating, without repetitions, all triangulationsand non-crossing geometric spanning trees on a given set of n points in the planeunder edge inclusion constraint (i.e., some edges are required to be included in thegraph). We will first extend the lexicographically ordered triangulations introduced byBespamyatnikh to the edge-constrained case, and then we prove that a set of all edge-constrained non-crossing spanning trees is connected via remove-add flips, based onthe edge-constrained lexicographically largest triangulation. More specifically, we provethat all edge-constrained triangulations can be transformed to the lexicographicallylargest triangulation among them by 0(n~2) greedy flips, i.e., by greedily increasing thelexicographical ordering of the edge list, and a similar result also holds for a set ofedge-constrained non-crossing spanning trees. Our enumeration algorithms generateeach output triangulation and non-crossing spanning tree in 0(log log n) and 0(n~2) time,respectively, based on the reverse search technique.