- 【Updated on May 12, 2025】 Integration of CiNii Dissertations and CiNii Books into CiNii Research
- Trial version of CiNii Research Automatic Translation feature is available on CiNii Labs
- Suspension and deletion of data provided by Nikkei BP
- Regarding the recording of “Research Data” and “Evidence Data”
Fast enumeration algorithms for non-crossing geometric graphs
Description
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.
Journal
-
- 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
Details 詳細情報について
-
- CRID
- 1050001202063097344
-
- NII Article ID
- 120001665857
- 120006653843
-
- ISSN
- 01795376
-
- HANDLE
- 2433/87301
- 2433/84844
-
- Text Lang
- en
-
- Article Type
- conference paper
-
- Data Source
-
- IRDB
- CiNii Articles
- KAKEN
- OpenAIRE
