Overview
In graph theory, the term blossom tree has two distinct but related meanings, depending on context.
1. Blossom Tree in Planar Graph Theory
In the study of planar graphs, a blossom tree is a tree with additional directed half-edges (called stems). Each blossom tree is associated with an embedding of a planar graph, and blossom trees can be used to sample random planar graphs.
Construction: A blossom tree is built 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 impose conditions on which kinds of stems they can carry. The terms leaves and blossoms are sometimes used for opening and closing stems, respectively.
Relationship with planar graphs: An embedded planar graph can be built from a blossom tree by connecting each opening stem to a closing stem. The process visits 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:
- If the type of the current half-edge matches the half-edge at the top of the stack, it is pushed onto the stack.
- If the types differ, the stack is popped and the two half-edges are connected.
This process takes linear time. Conversely, an embedding of a rooted planar graph can be encoded as a blossom tree in linear time (if the root is in a corner) or quadratic time (otherwise).
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 undercrossing. Blossom trees can generate random 4-regular planar graphs, though these do not always yield valid knot diagrams (there may be more than one component), which can be checked in cubic time.
2. Blossom Tree in Edmonds' Blossom Algorithm
In the context of matching theory, a blossom tree is a hierarchical data structure central to Edmonds' blossom algorithm (1965) for computing maximum cardinality or weighted matchings in general non-bipartite graphs.
Structure: It represents an alternating search tree rooted at an unmatched vertex, where nodes consist of graph vertices or contracted blossoms — odd-length alternating cycles treated as supervertices. The tree systematically searches for augmenting paths while handling odd cycles that violate bipartite assumptions.
Key features:
- Vertices are labeled even or odd based on distance from the root.
- A blossom forms when an edge connects two even-level vertices in the same tree, creating an odd alternating cycle that is contracted into a single node.
- The structure supports operations: growth (adding free edges from even levels), detection (identifying blossoms), and expansion (recursing inside contracted blossoms).
Complexity: The original implementation achieves O(n⁴) time complexity, but modern scaling techniques improve this to O(√n · m · log n) or better.
Applications: Combinatorial optimization, including approximations for the traveling salesman problem and structured updates in dynamic graphs.
References
- Wikipedia: Blossom tree (graph theory) (Text available under CC BY-SA)
- Edmonds, J. (1965). "Paths, Trees, and Flowers." Canadian Journal of Mathematics, 17: 449–467.
- Schaeffer, G. (1999). "Random sampling of planar maps." Combinatorics, Probability and Computing.
