Counting and Enumerating Crossing-free Geometric Graphs
Manuel Wettstein · 2014
We describe a framework for counting and enumerating various types of crossing-free geometric graphs on a planar point set. The framework generalizes ideas of Alvarez and Seidel, who used them to count triangulations in time O(2nn2) where n is the number of points. The main idea is to reduce the problem of counting geometric graphs to counting source-sink paths in a directed acyclic graph.