Construction (génération d'un arbre bourgeonnant)

On construit (de manière aléatoire ou autre), un mot binaire de longueur 4n et poids n (avec n symboles '1').
Ce mot constitue un codage d'un arbre plan à n sommets: en parcourant le contour de l'arbre, en partant de la racine en sens anti-horaire, on code avec un symbole '1' si l'on rencontre une arete interne de l'arbre une première fois; on écrit '0' pour les bourgeons, et aussi lorsqu'on rencontre une arete une deuxiè,e fois (en remontant dans l'arbre).

On construit l'arbre bourgeonnant à n sommets correspondant au mot binaire: si le mot est "correct" on obient un arbre plan à n sommets, où tous les sommets ont exactement deux bourgeons (fig. a)

Cloture partielle

En partant de la racine de l'arbre, on fait un parcours en profondeur (de gauche à droite) du contour de l'arbre: on renferme les bourgeons en sens horaire, de manière à créer des faces triangulaires (fig.(c) et (d) ).

Dernière étape: cloture complète

Une fois que tous les bourgeons ont été attachés, il ne reste qu'à ajouter deux sommets dans la face infinie, et relier les bourgeons incidents à la face externe (fig.(d) ) de manière à obtenir une triangulation planaire (fig.(e), (f) ).