For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Generating Biconnected Plane Quadrangulations
Zhang-Jian LI Shin-ichi NAKANO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2003/04/01
Print ISSN: 0916-8532
Type of Manuscript: PAPER
plane graphs, enumeration, listing,
Full Text: PDF>>
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(f3) time per quadrangulation.