Efficient generation of triconnected plane triangulations. (Q1428112)

Generating all graphs having some property without duplicates has many applications. The author gives a method for solving such tasks. It is an interesting open problem of this paper to use this method to give an algorithm for efficiently finding triangulations of a set of \(n\) given points on a plane or to solve other ``generate all of something'' tasks. Among others the following results are given in this paper: A ``rooted'' plane triangulation is a plane triangulation with one designed vertex on the outer face. A algorithm to generate all triconnected rooted plane triangulations with at most \(n\) vertices is presented. The algorithm does not output the entire triangulations but the difference from the previous triangulation and generates such triangulations in \(O(1)\) time per triangulation without duplications. All triconnected rooted plane triangulations having exactly \(n\) vertices including exactly \(r\) vertices on the outer face in \(O(r)\) time per triangulation can be generated without duplicates. An interesting result about such non-rooted plane triangulations is also obtained. All maximal planar graphs can be generated in cubic time per graph.