interactive · Baxter permutations ↔ mosaic floorplans

From a permutation to its mosaic and its bipolar orientation

Type any permutation. If it's Baxter, this reconstructs the actual mosaic floorplan (via Ackerman–Barequet–Pinter's direct O(n) construction), the Bonichon–Bousquet-Mélou–Fusy bipolar-orientation graph, and its vertex connectivity — live, all in your browser.

examples: octahedron (4-connected, n=11) smallest prime (n=5) vertical block (parallel edges, n=4) horizontal block (pass-through vertex, n=3)

The mosaic

Room k is the k-th room removed by bottom-left corner deletion. Colors match the graph edges at right. Every maximal vertical wall segment is a vertex of the same graph, seen a different way: every room is a directed edge from its left wall to its right wall.

The graph, at its actual bijection coordinates

Each vertex sits at its literal BBF coordinate wa = (a+½, ℓa+½). Every edge points strictly north-east by construction, so source and sink land at opposite corners for free.

Monotone meander

Baxter's own 1964 definition, geometrically. π (n rooms, ● filled) is first completed to a length-(2n−1) complete Baxter permutation by inserting n−1 connector points (○ hollow) — one between each pair of consecutive values i, i+1, at the unique split position required by Chung–Graham–Hoggatt–Kleitman's 1978 characterization §"THE FIRST RECURRENCE". Then ℓ1 (never moves left — the graph of a function) and ℓ2 (never moves down — the graph of a function, rotated 90°) thread through all 2n−1 points together, crossing exactly that many times and nowhere else. Each curve is a shape-preserving (PCHIP) spline through its own points plus one invisible "shadow" point per segment — the centroid of one half of the segment's bounding rectangle, chosen by alternating sides every step except at a direction reversal (where the alternation deliberately breaks instead of flips), with the two curves forced to opposite sides whenever they'd otherwise share the exact same two endpoints. Verified exactly: the completion algorithm reproduces Fusy's own worked example byte-for-byte, and this construction needs no extra crossing for every Baxter permutation of length 2–7 (0/2618, exhaustive).

Twin binary trees

Dulucq–Guibert's 1998 bijection. Insert π's values one at a time as an ordinary binary search tree (compare by value, no rebalancing): reading π left→right gives TL, reading it right→left gives TR. Every node's missing child is a "canopy" mark — empty left child, empty right child — and π is Baxter exactly when these two canopies are complementary: opposite at every one of the n−1 interior positions. Verified exhaustively for every Baxter permutation of length 2–7 (0/2618 mismatches).

Room ↔ edge correspondence

Room k is exactly black vertex bk = (k, π(k)) in the BBF bijection — its edge runs from the ascent dominating it to the ascent it dominates.

Every edge is directed. Φ(π) is a bipolar orientation: acyclic, one source, one sink, every edge running low-to-high in ascent order. Connectivity is computed on the undirected skeleton (plus a closing source→sink edge, the standard rooted-map convention) — it asks only whether the map itself can be pried apart, independent of which orientation/permutation you happen to have drawn.