IEICE TRANSACTIONS on Fundamentals
Listing All Connected Plane Triangulations
Summary :
A "rooted" plane triangulation is a plane triangulation with one designated vertex r and one designated edge incident to r on the outer face. In this paper we give a simple algorithm to generate all connected rooted plane triangulations with at most m edges. The algorithm uses O(m) space and generates such triangulations in O(1) time per triangulation without duplications. The algorithm does not output entire triangulations but the difference from the previous triangulation. By modifying the algorithm we can generate all connected (non-rooted) plane triangulations with at most m edges in O(m3) time per triangulation.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E86-A No.7 pp.1807-1812
- Publication Date
- 2003/07/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Algorithms and Data Structures
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, "Listing All Connected Plane Triangulations" in IEICE TRANSACTIONS on Fundamentals,
vol. E86-A, no. 7, pp. 1807-1812, July 2003, doi: .
Abstract: A "rooted" plane triangulation is a plane triangulation with one designated vertex r and one designated edge incident to r on the outer face. In this paper we give a simple algorithm to generate all connected rooted plane triangulations with at most m edges. The algorithm uses O(m) space and generates such triangulations in O(1) time per triangulation without duplications. The algorithm does not output entire triangulations but the difference from the previous triangulation. By modifying the algorithm we can generate all connected (non-rooted) plane triangulations with at most m edges in O(m3) time per triangulation.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e86-a_7_1807/_p
Copy
@ARTICLE{e86-a_7_1807,
author={Zhang-Jian LI, Shin-ichi NAKANO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Listing All Connected Plane Triangulations},
year={2003},
volume={E86-A},
number={7},
pages={1807-1812},
abstract={A "rooted" plane triangulation is a plane triangulation with one designated vertex r and one designated edge incident to r on the outer face. In this paper we give a simple algorithm to generate all connected rooted plane triangulations with at most m edges. The algorithm uses O(m) space and generates such triangulations in O(1) time per triangulation without duplications. The algorithm does not output entire triangulations but the difference from the previous triangulation. By modifying the algorithm we can generate all connected (non-rooted) plane triangulations with at most m edges in O(m3) time per triangulation.},
keywords={},
doi={},
ISSN={},
month={July},}
Copy
TY - JOUR
TI - Listing All Connected Plane Triangulations
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1807
EP - 1812
AU - Zhang-Jian LI
AU - Shin-ichi NAKANO
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E86-A
IS - 7
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - July 2003
AB - A "rooted" plane triangulation is a plane triangulation with one designated vertex r and one designated edge incident to r on the outer face. In this paper we give a simple algorithm to generate all connected rooted plane triangulations with at most m edges. The algorithm uses O(m) space and generates such triangulations in O(1) time per triangulation without duplications. The algorithm does not output entire triangulations but the difference from the previous triangulation. By modifying the algorithm we can generate all connected (non-rooted) plane triangulations with at most m edges in O(m3) time per triangulation.
ER -
English
