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 going around the tree and connecting opening and closing stems with a stack.
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.