Generating Biconnected Plane Quadrangulations
-
- LI Zhang-Jian
- the Department of Computer Science, Faculty of Engineering, Gunma University
-
- NAKANO Shin-ichi
- the Department of Computer Science, Faculty of Engineering, Gunma University
Search this article
Description
A plane quadrangulation is a plane graph such that each inner face has exactly four edges on its contour. This is a planar dual of a plane graph such that all inner vertices have degree exactly four. A based plane quadrangulation is a plane quadrangulation with one designated edge on the outer face. In this paper we give a simple algorithm to generate all biconnected based plane quadrangulations with at most f faces. The algorithm uses O(f) space and generates such quadrangulations in O(1) time per quadrangulation without duplications. By modifying the algorithm we can generate all biconnected (non-based) plane quadrangulations with at most f faces in O(f^3) time per quadrangulation.
Journal
-
- IEICE transactions on information and systems
-
IEICE transactions on information and systems 86 (4), 698-703, 2003-04-01
The Institute of Electronics, Information and Communication Engineers
- Tweet
Keywords
Details 詳細情報について
-
- CRID
- 1573950402084213760
-
- NII Article ID
- 110003223268
-
- NII Book ID
- AA10826272
-
- ISSN
- 09168532
-
- Text Lang
- en
-
- Data Source
-
- CiNii Articles