Blossom tree (graph theory)
In the study of planar graphs, blossom trees are rooted trees with aditional directed half edges. Each blossom tree is associated with an embedding of a planar graph. Blossom trees can be used to sample random planar graphs.[1]
Description
A blossom tree is constructed from a rooted tree embedded in the plane by adding opening and closing stems to vertices. The number of opening and closing stems must match.[2]
Relationship with planar graphs
An embedded planar graph can be built from a blossom tree by connecting each opening stem to a closing stem. One visits the half-edges by going around the graph either clockwise or counter-clockwise starting at the root. The algorithm is analoguous to parenthesis matching. At each stage, if the color of the current half-edge is the same as the half edge at the top of the stack, is pushed onto the stack. If the colors differ, the stack is popped and the two half-edges are connected.[3]
References
- ^ Albenque, Marie; Poulalhon, Dominique (2015). "Generic method for bijections between blossoming trees and planar maps". arXiv:1305.1312v3.
- ^ Albenque, Marie. "Blossoming trees and planar maps" (PDF). Retrieved 21 December 2015.
- ^ Schaeffer, Gilles; Denise, Alain. "Conjugation of trees and random maps" (PDF). Retrieved 21 December 2015.