Blossom tree (graph theory)

In the study of planar graphs, blossom trees are trees with additional 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 clockwise starting at an opening stem. If the tree is rooted, one usually starts at the root. The algorithm is analogous 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. This process takes linear time.

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 stem and inward half-edge as an opening stem. 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. If the map is not rooted in a corner, constructing the blossom tree takes quadratic time.

Use in knot theory

Blossom trees are also used to randomly generate large knot diagrams. Knots can be represented by 4-regular planar graphs where each node is marked as an overcrossing or undercrossings. Blossom trees can be used to generate random 4-regular planar graphs. However, these do not always give knot diagrams as there may be more than one component. This can be checked in cubic time.