| Fast enumeration algorithms for non-crossing geometric graphs (2008) | |||||||||||
Abstract | |||||||||||
| Proceedings of the twenty-fourth annual symposium on Computational geometry 2008, College Park, MD, USA, June 09-11, 2008. Proc. 24th Annual Symposium on Computational Geometry (SoCG 2008). Proc. 24th Annual Symposium on Computational Geometry (SoCG 2008). A non-crossing geometric graph is a graph embedded on a given set of points in the plane with non-crossing straight line segments. In this paper we present a new general framework for enumerating non-crossing geometric graphs for a given point set. By applying our idea to specific enumeration problems, we obtain faster algorithms for enumerating plane straight-line graphs, non-crossing spanning connected graphs, non-crossing spanning trees and non-crossing minimally rigid frameworks. Furthermore, we also obtain efficient enumeration algorithms for non-crossing geometric graph classes, for which no enumeration algorithm has been reported so far, such as non-crossing matchings, non-crossing blue-and-red matchings, non-crossing k-vertex or k-edge connected graphs or non-crossing directed spanning trees. The proposed idea is relatively simple, and can be potentially applied to various other enumeration problems of non-crossing geometric graphs. | |||||||||||
Publication details | |||||||||||
| |||||||||||