Module planar_separator 

Lipton-Tarjan style planar separator (1979).

Given a (planar) graph on n vertices, computes a vertex separator S together with a partition of the remaining vertices into A and B such that

• there is no edge between A and B (removing S disconnects them),
• each side is balanced: |A| <= 2n/3 and |B| <= 2n/3.

Construction (scope)

This is a compact realisation of the Lipton-Tarjan program, built from the two ingredients the theorem relies on, chosen per input:

• BFS levelling (the heart of Lipton-Tarjan). Run a breadth-first search from a root. Because every edge of a BFS-layered graph joins vertices in the same or adjacent levels, deleting one entire level l separates the strictly-lower levels from the strictly-higher levels. The median level always balances both sides below n/2 <= 2n/3; among all levels that keep both sides within 2n/3 we pick the smallest one as the separator. On a sqrt(n) x sqrt(n) grid the BFS levels are anti-diagonals of size O(sqrt(n)), giving the textbook O(sqrt(n)) separator.

• Tree centroid specialisation. For a tree (the degenerate planar case) the BFS-level separator can be as large as n/2, yet a single centroid vertex already splits every branch below n/2. When the input component is a tree we therefore return the centroid (a size-1 separator) and balance its branches into A/B with an exact subset-sum partition.

Disconnected inputs are handled component-wise. The balance and “no A-B edge” guarantees hold for every input; the O(sqrt(n)) size guarantee is for the planar classes exercised in the tests (grids, trees, paths), matching the latitude of the assignment.

Structs

PlanarSeparator

Planar separator solver over an undirected graph.

SeparatorResult

The three parts of a separator decomposition. Together they partition 0..n with no edge crossing between SeparatorResult::part_a and SeparatorResult::part_b.