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
この論文をさがす
説明
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.
収録刊行物
-
- IEICE transactions on information and systems
-
IEICE transactions on information and systems 86 (4), 698-703, 2003-04-01
一般社団法人電子情報通信学会
- Tweet
キーワード
詳細情報 詳細情報について
-
- CRID
- 1573950402084213760
-
- NII論文ID
- 110003223268
-
- NII書誌ID
- AA10826272
-
- ISSN
- 09168532
-
- 本文言語コード
- en
-
- データソース種別
-
- CiNii Articles