Case study 02 / 04
erlayout
Lays out ER diagrams with the fewest possible line crossings, and gives a proof.

Context
erlayout turns a database schema (SQL DDL, DBML or JSON) into an ER diagram. It is a Python package with a command line, and a hosted demo at erlayout.app where you paste a schema and watch the layout improve.
The problem
The usual layered method for drawing diagrams leaves line crossings that a better layout would avoid, and it can't tell you whether a layout is any good. I wanted the fewest crossings possible, and evidence that it was the fewest.
Approach
- 01
Choosing the columns and the vertical order of every table is treated as one problem and handed to an exact constraint solver (OR-Tools CP-SAT), instead of placing tables one step at a time.
- 02
The solver returns either a layout proven optimal, or the best layout found together with a proven lower bound. You always know how close to perfect the result is.
- 03
It ships as a package on PyPI with CI, runs the same interface locally with erlayout serve, and the hosted demo caps each solve at 5 minutes and runs two at a time.
Outcome
On the Sakila sample database (15 tables, 22 foreign keys), the standard layered layout has 8 crossings. erlayout gets 2 with rows as declared, proven to be the minimum, and 0 when rows can be reordered.