Id: palomar/PALOMAR-2026-11-21-000007 Url: https://github.com/RBarish-UTokyo/PlanarSeparator-NestedDissection-WordRAM-Lean4/tree/0b5373fd782ef11c5b049f03fa69506948092c05 Json: https://data.palomar-registry.org/entries/PALOMAR-2026-11-21-000007-v1.json Repo: https://github.com/RBarish-UTokyo/PlanarSeparator-NestedDissection-WordRAM-Lean4 Tags: math.CO, cs.DS, msc:05C10, msc:05C85, msc:65F05, msc:65F50, msc:68Q25, msc:68W40 Score: 0 Title: The planar separator theorem and nested dissection, with a linear-time separator program on a word RAM, in Lean 4 Trust: high Domain: math.CO Source: palomar Authors: Robert D. Barish Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Verified: true Discussed: 0 Published: 2026-11-21 Formalized: true Formalizes: title=A separator theorem for planar graphs identifier= relationship=adapts Formalizes: title=Generalized nested dissection identifier= relationship=adapts Formalizes: title=Algorithmic aspects of vertex elimination on graphs identifier= relationship=formalizes Page: https://delphi.science/r/palomar/PALOMAR-2026-11-21-000007 A Lean 4 and Mathlib formalization of the planar separator theorem of Lipton and Tarjan and of nested dissection. A plane graph is a Mathlib simple graph on a finite vertex type with a rotation system (a permutation of the darts cycling the darts at each vertex) such that the graph is connected and Euler's formula |V| + |F| = |E| + 2 holds for the set F of faces (so it has at least one edge: faces are cycles of darts, and the one-vertex graph has none). Eight theorems are compared: (1) the separator theorem with constant 6: for nonnegative vertex weights of total at most 1, a set of at most…