Fast enumeration algorithms for non-crossing geometric graphs
説明
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.
収録刊行物
-
- Proceedings of the twenty-fourth annual symposium on Computational geometry (SoCG 2008)
-
Proceedings of the twenty-fourth annual symposium on Computational geometry (SoCG 2008) 42 (3), 328-337, 2008
Association for Computing Machinery
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1050001202063097344
-
- NII論文ID
- 120001665857
- 120006653843
-
- ISSN
- 01795376
-
- HANDLE
- 2433/87301
- 2433/84844
-
- 本文言語コード
- en
-
- 資料種別
- conference paper
-
- データソース種別
-
- IRDB
- CiNii Articles
- KAKEN
- OpenAIRE
