I made ER diagrams with the fewest line crossings, and proved it

I was modelling the ER diagram for a new project, and it got messy quickly once I had to share it with other people. Lines crossed everywhere, and nobody could follow which table pointed where. Auto-layout tools place the boxes sensibly, but the ones I have used don't count how many relationship lines cross, so nothing stops the mess.

So I built erlayout to do that one thing: lay out an ER diagram with the fewest possible line crossings, and then prove that no layout in its model could do better.

• Demo: erlayout.app
• Code: github.com/ore-codes/erlayout
• Install: pip install erlayout

What it does

You give it SQL DDL, DBML (the format dbdiagram.io uses) or JSON. It chooses the column each table sits in and the vertical order of the tables within each column, together, so that as few lines as possible cross. Then it tells you what it can promise about the result.

Here is the Sakila sample database (15 tables, 22 foreign keys), with every crossing circled in red.

Usual layered layout	erlayout, rows as declared	erlayout, rows reordered
8 crossings	2 crossings, proven minimum	0 crossings

The "usual layered layout" is the classic pipeline: longest-path layering, then barycenter sweeps to order each column. The middle column keeps every table's columns in the order the schema declares. The third lets erlayout also reorder the rows that carry foreign keys, which is opt-in because it changes how your tables read.

The same pattern holds on the other sample schemas I tried: Chinook goes from 1 crossing to 0 and Northwind from 4 to 0, both proven optimal.

How it works

The drawing model. Tables sit in vertical columns. A foreign key joins one row of a table to one row of a table in a different column, and it leaves each table on the side facing the other. In the gap between two neighbouring columns, every line is a smooth left-to-right curve. That gives a simple rule: two lines in the same gap cross exactly once if their top-to-bottom order is inverted between the two sides of the gap, and never otherwise.

So a layout is purely combinatorial: a column per table and an order per column. Counting crossings becomes counting inverted pairs:

# simplified: edges e and f both span gap g
crosses = (key(e, g) - key(f, g)) * (key(e, g + 1) - key(f, g + 1)) < 0
# key = (position of the table or pass-through slot, row within the table)

The solver. I encode this as a Boolean model for Google's OR-Tools CP-SAT solver: which column each table is in, whether one item is above another in a column (kept transitive), and a variable per pair of edges and gap that is true when they cross. The objective is the sum of those variables. A second pass then shortens the lines without adding crossings.

The proof. If CP-SAT finishes with an optimum at K columns, nothing with at most K columns beats it. To cover every width, erlayout uses a neat fact: delete some tables from any drawing and what remains is a valid drawing of the smaller schema, with no more crossings. So if a small sub-schema needs c crossings in every drawing, the whole schema needs at least c. For Sakila, a 6-table sub-schema already forces 2 crossings, so the 2-crossing layout is optimal over every layered drawing, not just the widths the solver tried.

Checking the checker. A claim of optimality needs trust, so every result is re-checked by code that shares nothing with the solver: a combinatorial recount, and a geometric test that intersects the actual drawn curves and also checks that no line passes through a table. The test suite (268 tests) also compares the solver against exhaustive enumeration on random small schemas.

The full walkthrough, with the variables and the search phases, is in docs/solver.md.

Bigger schemas

An exact solver does not scale to hundreds of tables, and a drawing that large would not be readable anyway. Above 40 tables, erlayout splits the schema into groups of tables that reference each other a lot, solves each group as its own diagram, and arranges the diagrams in a grid. A link between two groups is not drawn as a line; the row says where it goes, for example → orders (group 3). Tables that reference everything (users, stores) can be hidden the same way, which removes the fans of lines they cause.

The price: proofs hold per diagram, not for the whole schema.

Take it with you

The result can be exported to draw.io (links attached to rows, so they follow a table you drag), Excalidraw and Mermaid, so erlayout can give you a good starting layout that you keep editing. If you start from dbdiagram.io, there is a short guide.

pip install erlayout
erlayout layout schema.sql -o er.svg -o er.drawio --time 120
erlayout serve        # the same web interface as the demo, on your machine

The search is anytime: a usable diagram appears within about a second and the file is rewritten each time a better layout is found, so you can stop whenever it looks good enough.

Honest limits

• "Optimal" is relative to the layered model above. A freer drawing could beat it.
• Exact solving is practical up to a few dozen tables.
• On dense schemas the solver finds good layouts but often cannot prove them. In my benchmark of random dense schemas of 10 to 12 tables, four runs ended with the best layout at 7 to 9 crossings and no proven lower bound at all. The result then says "best found" rather than "proven optimal", and it never claims more than it has shown.
• The demo caps each run at 5 minutes and two at a time. The pip package has no such limit.

Help wanted

I opened seven issues, labelled by size, for people who'd like to try:

• Good first: draw self-referencing foreign keys as loops, read Mermaid erDiagram input, export to PNG.
• Medium: let lines leave a table from either side (it might remove Sakila's last crossings), a Laravel migrations adapter.
• Hard: stronger lower bounds for dense schemas, and better groups when splitting large schemas.

CONTRIBUTING.md explains the setup, and the solver doc above tells you which file does what.

If you try it on your own schema, I'd like to hear how it went, especially if the result looks wrong. Open an issue, or tell me in the comments.