Graph of triangulations of a convex polygon and tree of triangulations
type: Item
instance of: scholarly article
title: Graph of triangulations of a convex polygon and tree of triangulations
zbMATH Open document ID: 0948.68127
DOI: 10.1016/S0925-7721(99)00016-4
author: Marc Noy
author: Ferran Hurtado
published in: Computational Geometry
publication date: 2000-11-13T00:00:00Z
review text: Define a graph \(G_T(n)\) with one node for each triangulation of a convex \(n\)-gon. Place an edge between each pair of nodes that differ by a single flip: two triangles forming a quadrilateral are exchanged for the other pair of triangles forming the same quadrilateral. In this paper there is introduced a tree of all triangulations of polygons with any number of vertices which gives a unified framework in which several results on \(G_T(n)\) admit new and simple proofs.
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1389795
zbMATH Keywords: simple polygon
zbMATH Keywords: triangulation
zbMATH Keywords: flipping
zbMATH Keywords: binary tree
zbMATH Keywords: rotation
zbMATH Keywords: outerplanar graph
zbMATH Keywords: Hamiltonian graph
reviewed by: Stanislav Jendroľ
MaRDI profile type: Publication
Wikidata QID: Q126550469
full work available at URL: s0925-7721(99)00016-4
OpenAlex ID: W1983134817
Recommended article: Geometric tree graphs of points in convex position
Recommended article: On trees of polygons
Recommended article: On the representation of triangulation graphs in trees
Recommended article: Q3754019
Recommended article: Q5221066
Recommended article: Q4204182
Recommended article: Q4331201
Recommended article: On Intersection Graphs of Convex Polygons
Recommended article: Triangulated edge intersection graphs of paths in a tree
Recommended article: Convex Polygons in Geometric Triangulations
description: scientific article; zbMATH DE number 1389795