← All work

Case study 02 / 04

erlayout

Lays out ER diagrams with the fewest possible line crossings, and gives a proof.

Category
Developer tool
Role
Design and development
Year
2026
Stack
  • Python
  • OR-Tools CP-SAT
  • PyPI
An ER diagram of the Sakila database laid out by erlayout with zero line crossings.

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

  1. 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.

  2. 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.

  3. 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.