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.

Description

A blossom tree (opening stems are in red, closing stems in blue)

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. Some authors require that blossom trees be rooted and put conditions on which kind of stems they can carry. The terms leaves and blossoms are also sometimes used for opening and closing stems.

Relationship with planar graphs

The planar graph obtained from the blossom tree above. The green lines connect the opening and closing stems.

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 starting at an opening stem. If the tree is rooted, one usually starts at the root. The algorithm is analoguous to parenthesis matching and uses a stack. At each stage, if the type of the current half-edge $s$ is the same as the half edge at the top of the stack, $s$ is pushed onto the stack. If the colors differ, the stack is popped and the two half-edges are connected. If we orient the added edges from opening to closing stem, we have no counter-clockwised edges.

Similarly, an embedding of a rooted planar graph can be encoded as a blossom tree. If the root is in the corner, this can be done in linear time. The edges of a rooted planar graph can be oriented so that there is a path from the root to any vertex, but there are no counter-clockwise cycles. In this case, one can use a depth-first algorithm to turn it into a blossom tree. Starting with the root vertex, look at every edge incident to it. If it points away from our current vertex, cut it, labelling the outward half-edge as a closing stems and inward half-edge as a opening stems. If it points toward our current vertex, mark it as to be kept and set its other endpoint as our current vertex. Continue until all edges have been considered.