Explore / Methods & Algorithms / Floorplanning / O-Tree

O-Tree

Floorplanning research 1999 Guo, Cheng, Otten tiny encoding linear decode compacted floorplans only

The idea

Restrict attention to admissible packings: those where no block can slide further left or down. Every good final floorplan is admissible, because slack on the left or bottom is wasted area. In such a packing, every block's left edge leans on something: another block's right edge, or the die wall. That leaning relation is a tree, the die wall is the root, and each block's parent is the block it abuts on the left.

The O-tree records exactly this ordered tree. Its shape encodes in 2n bits as a bracket sequence (descend to a child = open, ascend = close), plus the block permutation in traversal order:

O-tree size = 2n (tree shape) + n log n (permutation) = n(2 + log n) bits

2n the tree shape, one open and one close bracket per block
n log n the permutation of block names, log n bits each
this is the smallest encoding of any classic floorplan representation

Decoding walks the tree depth-first. A block's x-coordinate is its parent's right edge; its y-coordinate is found by pushing it down onto the contour, the skyline of everything placed so far. The contour is maintained so each placement costs amortized constant time, making the whole decode linear. Moves are tree surgeries: delete a subtree and reinsert it elsewhere.

The recipe

Step 1 (encode). Record the left-edge leaning tree as a bracket sequence plus a block permutation.

Step 2 (traverse). Walk the tree depth-first in the permutation order.

Step 3 (place). Set each block's x to its parent's right edge, and its y to the contour height over its width, then update the contour.

Step 4 (perturb). For annealing, delete a subtree and reinsert it elsewhere, alternating horizontal and vertical tree views.

Watch it work: leaning tree and contour decode

Four blocks in an admissible packing. The walkthrough shows the left-edge leaning that defines the tree, the tree and its bracket encoding, and the depth-first decode that pushes each block down onto the contour.

Why go through the tree at all? The point is not to draw one floorplan. A floorplanner searches over millions of candidate arrangements, and it needs each candidate to be cheap to store, cheap to change, and legal by construction. The O-tree is built for exactly that:

The tree is the small thing you search over, not the packing. The annealer never stores or edits x,y coordinates. It edits the tree, which is just the horizontal "who-leans-on-whom" order in a handful of bits. One move is "detach a subtree and reattach it under a different parent," meaning "make this block lean on a different block."
The packing is regenerated, never kept. The tree records only horizontal order. Vertical position is thrown away and recomputed at decode time by dropping each block down onto the contour (the skyline of what is already placed). So the expensive part, the actual coordinates, is derived on demand from the cheap part.
Every decode is already legal. Because x comes from the parent's right edge and y comes from resting on the contour, no two blocks can overlap and no gaps are left on the left or bottom. There is no separate legalization or overlap-removal pass, and the whole decode is linear time.

That is the payoff of the round trip: mutate a tiny tree, decode a guaranteed-legal packed floorplan in linear time, score it, keep or reject, repeat. The tree carries the state; the contour rebuilds the geometry.

Pros, cons, and the trade-off

Strengths

Smallest encoding: n(2 + log n) bits, less than any other classic representation.
Linear decode: the contour makes each placement amortized constant time.
Packed search space: it represents only admissible (compacted) floorplans, so every state is a candidate a designer would accept for area.

Weaknesses

Compacted only: it cannot express floorplans that need slack, such as whitespace targets or fixed pin positions.
Asymmetric: the tree captures horizontal abutment directly while vertical positions emerge from the contour, an asymmetry its successor removed.
Tree-surgery moves: deleting and reinserting subtrees is more involved than a name swap.

The trade-off

The O-tree trades expressiveness for efficiency. By representing only admissible packings it gets the smallest encoding and a linear decode, and every state is already compacted. The cost is that it cannot describe floorplans with deliberate slack, and its horizontal-vertical asymmetry makes some moves awkward, both of which its direct descendant, the B*-tree, set out to fix.

Is it actually used today?

The evidence for the O-tree is chiefly through its descendant and in the literature.

Through the B-tree: the B-tree took the O-tree's compacted-packing philosophy, bound it to a binary tree, and became the representation of choice for a generation of packers. Read that page next.
Literature: a standard reference point in floorplan-representation studies, cited for its minimal encoding and linear decode.