
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Efficient Generation of Plane Triangulations with a Degree Constraint
Hiroyuki TANAKA Zhangjian LI Shinichi NAKANO
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E86A
No.4
pp.829834 Publication Date: 2003/04/01
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section of Selected Papers from the 15th Workshop on Circuits and Systems in Karuizawa) Category: Keyword: graph, algorithm, plane graph, generation,
Full Text: PDF(271.2KB)>>
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 (nonbased) plane triangulations with exactly n vertices and maximum degree at most D in O(n^{3}) time per triangulation without duplications.

