Efficient Generation of Plane Triangulations with a Degree Constraint

概要

論文の詳細を見る
A "based" plane triangulation is a plane triangulation with one designated edge on the onter 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^3) time per triangulation without duplications.
社団法人電子情報通信学会の論文
2003-04-01