Efficient generation of triconnected plane triangulations.
type: Item
instance of: scholarly article
title: Efficient generation of triconnected plane triangulations.
zbMATH Open document ID: 1041.65022
author: Shin-Ichi Nakano
published in: Computational Geometry
publication date: 2004-03-14T00:00:00Z
review text: 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.
reviewed by: Hans-Dietrich Hecker
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 2056259
zbMATH Keywords: plane triangulations
zbMATH Keywords: rooted triangulations
zbMATH Keywords: algorithm
zbMATH Keywords: listing
zbMATH Keywords: plane graphs
MaRDI profile type: Publication
full work available at URL: j.comgeo.2003.06.001
OpenAlex ID: W2024428991
cites work: Generating rooted triangulations without repetitions
cites work: Constant Time Generation of Rooted Trees
cites work: Efficient Algorithms for Listing Combinatorial Structures
cites work: Q4148000
cites work: Q4522102
cites work: Isomorph-Free Exhaustive Generation
cites work: Constant Time Generation of Free Trees
DOI: 10.1016/J.COMGEO.2003.06.001
description: scientific article; zbMATH DE number 2056259