Listing All Connected Plane Triangulations

Zhang-Jian LI; Shin-ichi NAKANO

Listing All Connected Plane Triangulations

Zhang-Jian LI, Shin-ichi NAKANO

Full Text Views

0

Cite this

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(m³) 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

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(m³) 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(m³) 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(m³) time per triangulation.
ER -