{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"verified":true,"discussed":0,"published":"2026-11-21","reactions":{},"formalized":true,"formalizes":[{"title":"A separator theorem for planar graphs","identifier":"","relationship":"adapts"},{"title":"Generalized nested dissection","identifier":"","relationship":"adapts"},{"title":"Algorithmic aspects of vertex elimination on graphs","identifier":"","relationship":"formalizes"}]}