IEICE TRANSACTIONS on Information
Generating Biconnected Plane Quadrangulations
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E86-D No.4 pp.698-703
- Publication Date
- 2003/04/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Algorithms
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Zhang-Jian LI, Shin-ichi NAKANO, "Generating Biconnected Plane Quadrangulations" in IEICE TRANSACTIONS on Information,
vol. E86-D, no. 4, pp. 698-703, April 2003, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e86-d_4_698/_p
Copy
@ARTICLE{e86-d_4_698,
author={Zhang-Jian LI, Shin-ichi NAKANO, },
journal={IEICE TRANSACTIONS on Information},
title={Generating Biconnected Plane Quadrangulations},
year={2003},
volume={E86-D},
number={4},
pages={698-703},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={April},}
Copy
TY - JOUR
TI - Generating Biconnected Plane Quadrangulations
T2 - IEICE TRANSACTIONS on Information
SP - 698
EP - 703
AU - Zhang-Jian LI
AU - Shin-ichi NAKANO
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E86-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - April 2003
AB - 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.
ER -
English
