n vertices and with the maximum degree exactly D. The algorithm uses O(n) space and generates such triangulations in O(1) time per triangulation without duplications." />


Efficient Generation of Plane Triangulations with Specified Maximum Degree

Hiroyuki TANAKA  Shin-ichi NAKANO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E87-D   No.2   pp.330-336
Publication Date: 2004/02/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
graph,  algorithm,  plane graph,  generation,  

Full Text: PDF(314.6KB)>>
Buy this Article




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 having exactly n vertices and with the maximum degree exactly D. The algorithm uses O(n) space and generates such triangulations in O(1) time per triangulation without duplications.