Blossom tree (graph theory)
In the study of planar graphs, blossom trees are 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] Some authors require that blossom trees be rooted and put conditions on which kind of stems they can carry.[3] The terms leaves and blossoms are also sometimes used for opening and closing stems.[3][4]
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. If the tree is rooted, one usually starts 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.[4]
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.
- ^ a b Calvo, Jorge Alberto (2005-01-01). Physical and Numerical Models in Knot Theory: Including Applications to the Life Sciences. World Scientific. ISBN 9789812703460.
- ^ a b Schaeffer, Gilles; Denise, Alain. "Conjugation of trees and random maps" (PDF). Retrieved 21 December 2015.