Efficient Generation of Plane Triangulations with a Degree Constraint

Hiroyuki TANAKA; Zhangjian LI; Shin-ichi NAKANO

Efficient Generation of Plane Triangulations with a Degree Constraint

Hiroyuki TANAKA, Zhangjian LI, Shin-ichi NAKANO

Full Text Views

0

Share
Cite this

Summary :

A "based" plane triangulation is a plane triangulation with one designated edge on the outer face. In this paper we give a simple algorithm to generate all biconnected based plane triangulations with at most n vertices and with maximum degree at most D. The algorithm uses O(n) space and generates such triangulations in O(1) time per triangulation without duplications. The algorithm does not output entire triangulation but the difference from the previous triangulation. By modifying the algorithm we can generate all biconnected based plane triangulations with exactly n vertices and maximum degree at most D in O(1) time per triangulation, and all biconnected (non-based) plane triangulations with exactly n vertices and maximum degree at most D in O(n³) time per triangulation without duplications.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E86-A No.4 pp.829-834

Publication Date: 2003/04/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section of Selected Papers from the 15th Workshop on Circuits and Systems in Karuizawa)

Category

Cite this

Copy

Hiroyuki TANAKA, Zhangjian LI, Shin-ichi NAKANO, "Efficient Generation of Plane Triangulations with a Degree Constraint" in IEICE TRANSACTIONS on Fundamentals, vol. E86-A, no. 4, pp. 829-834, April 2003, doi: .
Abstract: A "based" plane triangulation is a plane triangulation with one designated edge on the outer face. In this paper we give a simple algorithm to generate all biconnected based plane triangulations with at most n vertices and with maximum degree at most D. The algorithm uses O(n) space and generates such triangulations in O(1) time per triangulation without duplications. The algorithm does not output entire triangulation but the difference from the previous triangulation. By modifying the algorithm we can generate all biconnected based plane triangulations with exactly n vertices and maximum degree at most D in O(1) time per triangulation, and all biconnected (non-based) plane triangulations with exactly n vertices and maximum degree at most D in O(n³) time per triangulation without duplications.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e86-a_4_829/_p

Copy

@ARTICLE{e86-a_4_829,
author={Hiroyuki TANAKA, Zhangjian LI, Shin-ichi NAKANO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Efficient Generation of Plane Triangulations with a Degree Constraint},
year={2003},
volume={E86-A},
number={4},
pages={829-834},
abstract={A "based" plane triangulation is a plane triangulation with one designated edge on the outer face. In this paper we give a simple algorithm to generate all biconnected based plane triangulations with at most n vertices and with maximum degree at most D. The algorithm uses O(n) space and generates such triangulations in O(1) time per triangulation without duplications. The algorithm does not output entire triangulation but the difference from the previous triangulation. By modifying the algorithm we can generate all biconnected based plane triangulations with exactly n vertices and maximum degree at most D in O(1) time per triangulation, and all biconnected (non-based) plane triangulations with exactly n vertices and maximum degree at most D in O(n³) time per triangulation without duplications.},
keywords={},
doi={},
ISSN={},
month={April},}

Copy

TY - JOUR
TI - Efficient Generation of Plane Triangulations with a Degree Constraint
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 829
EP - 834
AU - Hiroyuki TANAKA
AU - Zhangjian LI
AU - Shin-ichi NAKANO
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E86-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 2003
AB - A "based" plane triangulation is a plane triangulation with one designated edge on the outer face. In this paper we give a simple algorithm to generate all biconnected based plane triangulations with at most n vertices and with maximum degree at most D. The algorithm uses O(n) space and generates such triangulations in O(1) time per triangulation without duplications. The algorithm does not output entire triangulation but the difference from the previous triangulation. By modifying the algorithm we can generate all biconnected based plane triangulations with exactly n vertices and maximum degree at most D in O(1) time per triangulation, and all biconnected (non-based) plane triangulations with exactly n vertices and maximum degree at most D in O(n³) time per triangulation without duplications.
ER -