Generating Biconnected Plane Quadrangulations

Zhang-Jian LI  Shin-ichi NAKANO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E86-D   No.4   pp.698-703
Publication Date: 2003/04/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithms
Keyword: 
plane graphs,  enumeration,  listing,  

Full Text: PDF>>
Buy this Article




Summary: 
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.