Lecture Notes in Computer Science, 2001, Volume 2076/2001, 433-443, DOI: 10.1007/3-540-48224-5_36

Efficient Generation of Plane Triangulations without Repetitions

Zhangjian Li and Shin-ichi Nakano

View Related Documents

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. The algorithm uses O(n) 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 biconnected based plane triangulation having exactly n vertices including exactly r vertices on the outer face in O(1) time per triangulation without duplications, while the previous best algorithm generates such triangulations in O(n 2) time per triangulation. Also we can generate without duplications all biconnected (non-based) plane triangulations having exactly n vertices including exactly r vertices on the outer face in O(r 2 n) time per triangulation, and all maximal planar graphs having exactly n vertices in O(n 3) time per graph.

Fulltext Preview

Image of the first page of the fulltext document