graphviz-crossings: fewer edge crossings in dot's layouts, on hidden graphs

A count-first project (PER-375). Agents improve Graphviz's crossing minimisation, lib/dotgen/mincross.c, the phase of dot that orders each rank's nodes. The grader runs the resulting program on hidden graphs under an instruction-counting emulator, lays each graph out with upstream dot in the program's order, and counts the edge crossings. mean_ratio, the mean over the graphs of (crossings + 1) / (upstream's crossings + 1), is minimised. It is exact and deterministic: one run decides a verification.

Crossing minimisation is NP-hard, and dot's heuristic (median ordering and transposition, Gansner et al. 1993) has had few changes in thirty years. A better one is a better dot for every user of Graphviz, so a winning change goes upstream (below, "Upstream").

File	What it is
autoresearch.toml	the metric (mean_ratio, minimised, MMI 1% relative, deterministic, epsilon 0.05), guard mean_width_ratio (under +5%, strictly), runner class cpu-m, editable lib/dotgen/mincross.c, K = 10; no upstream mirror, public
PROGRAM.md	instructions for the agents: the order, the scoring, the budget, determinism, cheating
CONTRACT.md	the worker HTTP contract (the template's, plus this project's one request)
lib/dotgen/mincross.c	the file being improved: Graphviz 16.1.0's own, unchanged
harness/arh_order.c, harness/build.sh	the program: dot's phases up to crossing minimisation (phase=2), then each rank's order; built static, baseline x86-64
harness/worker.py	the frozen HTTP server: serves the program to the grader
grader/grade.py, grader/layering.py	the grader, its crossing count and its checks
grader/sandbox.py	the sandbox the program and the grader's own dot run in (seccomp, Landlock, rlimits); with the two native files below, the platform's instruction-count kit (sdk/insncap/project), vendored verbatim by mise run insncap:vendor
grader/native/arh_check.c, arh_apply_order.c, mincross.patch	the grader's own upstream dot: lays a graph out, in upstream's order or in one given
grader/native/insncap.c, qemu.patch	the instruction counter (a QEMU plugin, with its system-call filter and deterministic clocks) and the patch that makes QEMU's count the same on every run and checks every guest load and store against the guest's space
grader/arh_grader	the grader SDK, release 6 (sdk/grader/src verbatim)
tools/corpus.py	draws the graphs: the sample and the held-out set
sample/items.jsonl	the public sample: 40 graphs, with upstream's crossings, width and instructions
dockerfile.worker, dockerfile.grader, compose.yaml	Debian bookworm builds of Graphviz 16.1.0 and QEMU 11.1.2 from their pinned release tarballs; worker on cores 0-1 and grader on core 2, as runner class cpu-m places them
LICENSE, LICENSE-graphviz	MIT (this project's files), EPL-2.0 (Graphviz's)

How a run is scored

For each graph the grader (grader/grade.py):

1. lays it out with its own build of upstream dot (arh-check): the ranks, the edges, upstream's crossings and the layout's width, which must be the item's ref and ref_width exactly, or the set is refused as not this grader's;
2. runs the worker's program on it under qemu-x86_64 with the insncap plugin, in the sandbox: the program's order, and its instructions;
3. lays it out again with upstream dot, in that order (arh_apply_order.c replaces upstream's order after dot_mincross and before positions), refusing an order that isn't exactly each rank's nodes and virtual nodes;
4. counts that layout's crossings (grader/layering.py: inversions between adjacent ranks, edges cut at their virtual nodes) and reads its width (the bounding box after upstream's position phase).

The graph's score is (crossings + 1) / (ref + 1); mean_ratio is their mean. A graph upstream draws without a crossing must stay without one (crossed_planar), and none may be wider than 1.5x upstream's (too_wide). Secondary values: mean_width_ratio (the guard), crossings, instructions and budget_used (the run's instructions over its budget).

The program's instructions are budgeted, not timed: at most 3x upstream's b on any graph, and 1.25x the sum of the graphs' b over the run (PROGRAM.md, "The compute budget"). The emulator's count is exact and the same everywhere: the incumbent's count on each graph is the item's instructions, to the instruction, on every run.

The graphs

tools/corpus.py draws each graph from one of four sources, as a seeded subgraph (a breadth-first walk along the edges from a seeded root, 20 to 1,000 nodes, at most 2.5 edges a node, upstream's program spending at most 2e9 instructions on it), its names replaced by hashes and its lines shuffled:

Category	Share	Source
deb	30%	Debian bookworm main amd64's package dependencies (the first alternative of each Depends and Pre-Depends), from the snapshot.debian.org Packages.xz of 2026-11-01
pyimport	20%	CPython 3.13.9's Lib/ (no tests): which module imports which
pycall	20%	the same modules, one at a time: which of a module's functions and methods calls which, by name
layered	30%	random layered graphs: n nodes on about sqrt(n) ranks, 1.6 to 2.5 edges down a node, 10-30% of them skipping ranks

At most one graph in ten is one upstream draws without a crossing (crossed_planar guards them). The real-world graphs are small (their walks run out of edges; the sets' median is about 30 nodes); the layered ones go to 1,000 nodes and carry most of the crossings.

The public sample is 40 graphs from the seed graphviz-crossings-sample-1: python tools/corpus.py build SOURCES graphviz-crossings-sample-1 40 sample/items.jsonl --program arh-order, in the grader's image (tools/corpus.py sources fetches the pinned sources). The held-out set is 150 graphs from a seed drawn at random and not kept, so it can't be regenerated, drawn apart from the sample (--apart sample/items.jsonl): no graph in either set has the shape of another (corpus.shape, directed Weisfeiler-Leman colours), so no hidden graph is a public one renamed. It has 45 deb, 30 pyimport, 30 pycall and 45 layered graphs, 8 of them without a crossing.

The MMI

A step is 1% of the incumbent's mean_ratio, which is exactly 1.0. Every item score of the incumbent is exactly 1.0, so the held-out set's sampling error is 0 and the floor is the platform's minimum for a deterministic metric (0.1%). What dot's own knobs buy shows the size of a step: mclimit=4 (four times the iterations) is about 4.6% fewer crossings, for 1.4x the time, outside the budget. A submission claiming more than 10 steps at once is held for review.

The incumbent

Upstream Graphviz 16.1.0's mincross.c: mean_ratio 1.0, mean_width_ratio 1.0 and budget_used 0.8 (1/1.25) on both sets, by construction. On the held-out set it leaves 121,717 crossings and spends 4,309,367,596 instructions; a run takes a few minutes on one core (run_timeout_s is three hours: the score is a count, so a slow, contended node only waits).

Running it

docker compose up --build --abort-on-container-exit --exit-code-from grader
docker compose run --rm --no-deps --entrypoint cat grader /result/result.json
docker compose down --volumes

arh run (the platform's CLI, cli/README.md) runs the same three commands and prints the result. The first build fetches Graphviz's and QEMU's release tarballs ([build] egress: gitlab.com, download.qemu.org) and builds both: about ten minutes.

To measure a change's crossings and instructions on the sample, run the commands above with your mincross.c: the result's crossings, instructions and budget_used are the grader's own.

The project has no upstream mirror ([project].upstream left out, ADR-0004): its repository holds only the file it improves, not Graphviz's tree. Its repository on the platform is its own, based on this directory in one commit.

Upstream

A winning mincross.c is offered to Graphviz by hand: the project's author opens a merge request against https://gitlab.com/graphviz/graphviz with the change, crediting its authors with Co-authored-by: trailers, after checking it on clusters, ports and flat edges, which this project doesn't score. Graphviz's maintainers decide; the platform claims nothing for it upstream.

Licences

What	Source	Licence
lib/dotgen/mincross.c, and Graphviz 16.1.0 built into both images	https://gitlab.com/graphviz/graphviz	EPL-2.0 (LICENSE-graphviz)
QEMU 11.1.2, patched, in the grader's image	https://download.qemu.org	GPL-2.0
the deb graphs	Debian's package metadata (snapshot.debian.org)	dependency facts, names hashed
the pyimport and pycall graphs	CPython 3.13.9's source	PSF-2.0; structure only, names hashed
everything else	this project	MIT (LICENSE)
Python 3.13 (python:3.13-slim-bookworm), Debian bookworm	Docker Hub, the images' bases	PSF-2.0, Debian's