ghist 0.20261114.2

An opinionated git log replacement with a Unicode graph
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
<!--
Copyright © 2026 Michael Shields

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-->

# Graph layout

This document explains why ghist’s lane graph draws what it draws: the model,
the results from graph drawing and online algorithms that apply to it, what
other tools do, and earlier measurements that inform the rules in
[the design](design.md#graph-layout). The short version: computing a better
layout is cheap, but knowing enough to choose it is not. ghist decides each
commit’s rows from that commit and the ones before it. It keeps first-parent
lines straight and connects incoming lanes at the commit they await.

## The model

Rows are fixed. Git’s `--topo-order` decides the order of commits, and every
commit’s rows are written before the next commit is read.

A lane is a column awaiting one commit. Its lifetime is an interval of rows,
from the commit that opens it to the awaited commit. Several lanes may await the
same commit; they meet at its dot. Lanes alive in the same row need different
columns. The first-parent chain of the first commit stays in column zero.

A connector is a horizontal span in one row: a fork from a commit to a new or
existing parent lane, a join, or a lane moving between columns. A connector
crosses every occupied column strictly between its ends, drawn as `│` between
`─` segments. Corners (`╭╮╯╰`) are bends.

Every first-parent edge continues straight down from the commit’s dot. An
existing lane for that parent stays open alongside it until the parent is shown.
Other parent connections reach their existing lanes on the commit row, or open
new lanes. Incoming connections end at the dot, and outgoing connections start
there. A row without a commit has no branching junctions.

The costs are crossings, bends, width, and rows. Width is paid on every text
line, because the text column is `2 × width + 1`, so the mean matters more than
the maximum. The lower bound on width at a row is the number of lanes alive
there, a property of Git’s order and not of the layout.

### Two lanes

Take two side lanes that fork from column zero and join it again, drawn in fixed
columns. Their crossings depend only on how their lifetimes relate:

| Lifetimes                           | Crossings                                    |
| ----------------------------------- | -------------------------------------------- |
| Disjoint                            | 0                                            |
| Interleaved: `s₁ < s₂ < e₁ < e₂`    | 1, whichever lane is outside                 |
| Nested: the second inside the first | 0 if the longer lane is outside, otherwise 2 |

So the minimum is the number of interleaved pairs, and a layout reaches it
exactly when column order respects nesting: the lane that ends later sits
further out. Brute force over 3,000 random instances of up to six lanes agreed
with this count every time.

Nesting can cost width. With `A = [0, 10] ⊃ B = [1, 2]` and
`C = [9, 20] ⊃ D = [11, 12]`, at most two lanes are alive at once, but
respecting both nests needs three columns: the best is three crossings at width
two or one crossing at width three.

First-fit, the rule “take the first free column,” gives the minimum width
because lanes arrive in order of their start. It is blind to nesting: the lane
that arrived first is innermost, even when it outlives everything that opens
inside it. On the large repositories measured below, 74–86% of first-fit’s
crossings were nested pairs drawn the wrong way round.

### What zero lookahead cannot do

For any rule that sees only a bounded number of commits ahead, two histories can
agree inside the window and differ after it:

- A merge opens lane `a`, and `a`’s commit is followed by linear commits.
- In one history, `a`’s parent comes next, so `a` belongs in column one.
- In the other, another merge opens a branch that ends inside `a`’s lifetime, so
  `a` belongs in column two with the newcomer inside it.

The rule sees the same rows in both. If it puts `a` in column one, the second
history pays a crossing, or two corners and a row to move `a` out. If it puts
`a` further out, the first history pays two characters of indentation on every
line until `a` ends. Repeating the gadget makes the loss grow without bound.
Each strategy pays in one currency:

| Strategy                                       | Pays         | Used by           |
| ---------------------------------------------- | ------------ | ----------------- |
| First free column                              | Crossings    | ghist, jj         |
| Insert new lanes at the commit, shift the rest | Bends, rows  | `git log --graph` |
| Reserve room inside every lane                 | Width        | None surveyed     |
| Look ahead or read the whole history           | Latency, CPU | IntelliJ, GitLab  |

## ghist’s rules

**Straight first parents.** A commit’s first parent continues in its column,
even when another lane awaits the same parent. Both lanes keep their columns
until that parent is printed. This keeps the first-parent chain of the first
commit in column zero and avoids detours that leave a dot horizontally only to
bend back into its column below it.

**Incoming edges meet at the dot.** When several lanes await a commit, the
leftmost carries the dot, and the others connect to it on that row. Those other
columns become holes only after the outgoing parents have been placed. Reusing
one immediately would make an incoming edge look as though it continued past the
commit into a different parent.

For example, two branches that await a merge’s first parent keep separate lines
until that parent is printed:

```text
●─┬─╮  tip
│ │ │
●─│─┤  merge
│ │ │
│ │ ●  side
│ │ │
●─┴─╯  parent
```

Additional merge parents may share an existing lane, connected on the merge’s
row. Unrelated lanes cross the horizontal connection without joining it. Keeping
first-parent lines separate can use more columns, but every join has a commit at
which to interpret it.

**Lazy compaction.** A hole is filled only after it has stayed empty for 20
commits. The rightmost lane moves into the first old hole with two bends and no
junction. This preserves the edges and bounds the cost of unused columns.

## Earlier lane-sharing rules

The measurements below cover an earlier layout that combined first-parent lanes
before reaching the awaited commit. Its three rules and their rationale are
retained here to explain those results; the current layout keeps those lanes
separate and retains only lazy compaction.

**Merge-tap.** A merge outside column zero whose first parent is already awaited
on its right taps that lane instead of pulling it in, if another parent opens a
new lane. The new lane then starts in the node column, and the fan-out is a
single connection (`●─┤`) instead of a crossing, a pull, and usually a later
jog.

**Sibling joins in a merge train keep the outer column.** Each lane records a
family, shared along the lanes that continue one line of history, and the family
of the lane that opened it. When a single-parent commit joins two lanes opened
by the same family, keeping the outer column instead of the inner one is a bet:
the freed inner column sits next to their opener, so the opener’s next branch
can start there, inside the long-lived lane, without crossing it. The commit
pulls a lane on its left into its own column, or taps a lane on its right. A
pull connects at the dot (`├─●`) and then moves the lane (`╰─╮`); a tap connects
to the surviving lane (`●─┤`). A bet that no branch takes leaves a hole that
compaction later fills with a jog, so the outer column is kept only when the
past says the bet will pay:

- the node lane’s family started after the parent lane’s, so a long-lived branch
  that rejoins younger lanes, as in git-flow, does not walk right one column per
  merge;
- the opener’s lane lies left of both lanes;
- the inner column would be the only hole left of the outer lane, so the next
  branch lands in it rather than in an older hole; and
- the opener opened lanes at two commits within the last five, a merge train in
  progress.

Merges keep the plain rule, because a merge’s other connectors can cross the
moved lane. The window counts every shown commit, including the branches’ own,
so a train of branches three or more commits long falls outside it and keeps
first-fit’s columns. Without the guards, the rule made 119,096 such joins on the
24 repositories first measured, these 23 and go-git; their freed columns were
almost always reused, but the outer lanes starved other holes, which aged and
were compacted, so jogs rose 62%. The hole guard matters most; the burst guard
removes the crossings the unguarded rule added on zigbee-herdsman-converters and
zigbee2mqtt; the age guard fixes git-flow.

**Lazy compaction.** A hole is filled only after it has stayed empty for 20
commits. Most holes are reused by a new lane within a few commits, so moving a
lane into them immediately draws a jog that the next fork would have made
unnecessary. This is a rent-or-buy decision: an open hole costs up to two
characters of indentation on each commit’s lines, while a jog costs two corners,
a row, and a crossing with every lane it passes. The wait is a point on a smooth
trade-off between width and jogs, not a tuned optimum.

The example that prompted these rules is four one-commit branches forked from
one commit `X` and merged one after another. First-fit placed the long-lived
lane for `X` innermost and crossed it at every merge after the first:

```text
first-fit         earlier ghist
●─╮               ●─╮
│ ●               │ ●
●─│─╮             ●─│─╮
│ ├─●             │ ├─●
│ │               │ ╰─╮
●─│─╮             ●─╮ │
│ ├─●             │ ●─┤
●─┼─╮             ●─┬─┤
╭─╯ │             ╭─│─╯
│ ╭─╯             ├─●
├─●               ●
●
```

The first crossing remains because nothing at the first merge says that `X`’s
lane will outlive the next branches. The last remains because a fan-out row
precedes a pull row: the last merge must open its branch before it can pull
`X`’s lane into column zero. Lookahead of a few commits would remove the first;
no layout removes the last.

## Measurements

These measurements describe the earlier lane-sharing rules above. They are not
measurements of the current layout, which retains separate first-parent lanes
until their target commit and can therefore use more width.

Measurements on October 9, 2026 used an Apple M1 Max, macOS 27.0.1, Rust 1.99.0,
and Git 2.56.0, on 23 local repositories chosen for their merges. Each figure
counts the graph prefixes of plain `ghist` output over the whole history:

- **Crossings:** `│` cells with a horizontal arm on both sides.
- **Corners:** `╭`, `╮`, `╯`, and `╰` cells.
- **Jogs:** compaction moves, which are the only rows that draw `╭`.
- **Graph rows:** rows with a horizontal connector.
- **Mean width:** each commit’s graph width in columns, holes included, averaged
  over commits.

First-fit with immediate compaction, then the earlier lane-sharing rules:

| Repository                         | HEAD       | Commits |             Crossings |           Corners |           Jogs |        Graph rows |    Mean width |
| ---------------------------------- | ---------- | ------: | --------------------: | ----------------: | -------------: | ----------------: | ------------: |
| shields/homebrew-cask              | `c22c1bcc` | 475,047 | 2,089,483 → 1,440,195 | 331,152 → 293,543 | 19,897 → 1,094 | 311,567 → 292,763 |   9.47 → 9.59 |
| Homebrew/brew                      | `1b0b73c8` |  53,057 |      108,545 → 76,530 |   42,508 → 31,427 |    5,732 → 191 |   37,020 → 31,479 |   5.43 → 5.79 |
| esphome/esphome                    | `d59c006f` |  13,835 |         1,499 → 1,451 |     1,094 → 1,072 |        32 → 24 |     1,362 → 1,351 |   3.58 → 3.62 |
| shields/zigbee-herdsman-converters | `0a47792a` |  13,814 |             170 → 107 |         172 → 138 |         17 → 0 |         178 → 161 |   1.07 → 1.07 |
| open-webui/open-webui              | `b03fc97e` |   9,279 |        14,468 → 8,924 |     4,542 → 3,300 |      549 → 116 |     4,409 → 3,787 |   6.77 → 7.29 |
| jindrapetrik/jpexs-decompiler      | `3d91020a` |   7,864 |             110 → 102 |         594 → 566 |         13 → 0 |         614 → 600 |   1.39 → 1.40 |
| ohmyzsh/ohmyzsh                    | `3e7ef018` |   7,548 |       45,238 → 26,899 |     3,716 → 3,233 |      358 → 120 |     3,490 → 3,248 | 14.58 → 15.14 |
| Koenkk/zigbee2mqtt                 | `b0b02c30` |   6,626 |               81 → 55 |         254 → 228 |         13 → 1 |         329 → 316 |   1.61 → 1.62 |
| shields/WLED                       | `dc7eb8f4` |   5,344 |        10,962 → 7,733 |     2,286 → 1,691 |       352 → 85 |     2,163 → 1,865 |   9.06 → 9.71 |
| shields/awesome-mcp-servers        | `b3089197` |   4,822 |       54,126 → 37,678 |     4,382 → 3,780 |      466 → 166 |     4,228 → 3,927 | 20.72 → 21.76 |
| exelban/stats                      | `68416572` |   2,131 |               23 → 20 |          100 → 90 |          5 → 0 |          101 → 96 |   1.15 → 1.17 |
| Luligu/matterbridge                | `00998e18` |   2,112 |         1,072 → 1,017 |         170 → 160 |        22 → 17 |         216 → 211 |   6.04 → 6.22 |
| shields/k9s                        | `ff76762d` |   2,029 |             414 → 348 |         504 → 390 |         56 → 4 |         476 → 419 |   2.24 → 2.39 |
| michaelrsweet/pappl                | `5495d919` |   1,727 |               33 → 22 |         138 → 128 |          5 → 0 |         138 → 133 |   1.40 → 1.43 |
| oraios/serena                      | `111a764b` |   1,311 |             315 → 273 |         382 → 318 |         34 → 3 |         393 → 361 |   3.11 → 3.29 |
| taiki-e/cargo-llvm-cov             | `f20c83f4` |   1,195 |               37 → 37 |         287 → 277 |          5 → 0 |         283 → 278 |   1.33 → 1.33 |
| awsdocs/aws-lambda-developer-guide | `7bb9f8ab` |     908 |         2,675 → 1,939 |         640 → 504 |        80 → 17 |         605 → 537 |   6.73 → 7.57 |
| shields/lgtmcp                     | `27e853af` |     366 |               45 → 39 |         172 → 166 |          3 → 0 |         190 → 187 |   1.76 → 1.78 |
| gitcalver/gitcalver.org            | `5448ffde` |     127 |                 0 → 0 |             6 → 6 |          0 → 0 |             6 → 6 |   1.06 → 1.06 |
| gitcalver/rust                     | `73ab4cf8` |      67 |                 2 → 2 |           18 → 16 |          1 → 0 |           17 → 16 |   1.30 → 1.30 |
| gitcalver/sh                       | `7120f81e` |      46 |                 2 → 2 |            10 → 8 |          1 → 0 |             9 → 8 |   1.35 → 1.35 |
| gitcalver/go                       | `78d58676` |      39 |                 1 → 1 |             6 → 6 |          0 → 0 |             7 → 7 |   1.31 → 1.31 |
| gitcalver/python                   | `65e0e589` |      36 |                 3 → 2 |            10 → 8 |          1 → 0 |             9 → 8 |   1.36 → 1.36 |

No repository is worse on crossings, corners, jogs, or graph rows. Each rule’s
effect, applied in order, summed over the 23 repositories:

| Rule                | Crossings | Corners |   Jogs | Graph rows | Mean width |
| ------------------- | --------: | ------: | -----: | ---------: | ---------: |
| First-fit           | 2,329,304 | 393,143 | 27,642 |    367,810 |      8.582 |
| Merge-tap           | 2,326,285 | 392,254 | 27,437 |    367,364 |      8.582 |
| Lazy compaction, 16 | 2,069,932 | 341,707 |  2,164 |    342,092 |      8.735 |
| Lazy compaction, 20 | 2,062,762 | 341,293 |  1,957 |    341,885 |      8.754 |
| Sibling joins       | 1,603,376 | 341,055 |  1,838 |    341,764 |      8.740 |

Overall, crossings fall 31%, corners 13%, jogs 93%, and graph rows 7%, while
mean width, weighted by commits, rises 1.8%. The widest commit gains a column
only on open-webui and loses one on zigbee2mqtt.

The thresholds were chosen on these repositories, so they were also checked on
480 histories generated in four styles: merge trains, git-flow, long feature
branches, and a mix. There, crossings fall 30%, corners 25%, jogs 89%, and graph
rows 13%, for 7.9% more width, and no history is worse than first-fit on any of
the four counts. Against the rules before it, the guarded sibling rule cuts
crossings 5.4% there, is better on 274 histories, and is worse on some count on
78, by small amounts; unguarded, it was worse on 267.

Most of the remaining crossings need the future to avoid. A Python model of
first-fit, which reproduced ghist’s rows exactly, attributed 74–86% of
first-fit’s crossings on the large repositories to nested pairs drawn inside
out, and a pairwise counting argument put the crossings that no layout keeping
column zero and drawing fan-outs before pulls can avoid at 0.3–9.3% of
first-fit’s.

The `GHIST_DIFF_REPOS` oracle in `tests/it/differential.rs` checked every header
and every drawn edge against Git on all of these repositories except
homebrew-cask.

## What lookahead would cost

Lookahead of `K` commits means drawing commit `i` only after Git has produced
commits up to `i + K`. These figures were measured with Git 2.56.0 on the same
machine while it was heavily loaded, so CPU times are more reliable than wall
times, and brew figures use the 43,936-commit checkout in
[the benchmarks](benchmarks.md):

- **Inside the one stream:** without `-p` or `--stat`, a window of `K` parsed
  records costs no extra process and about nothing in time. With `-p`, commit
  `i`’s patch sits between its fields and record `i + 1`, and its prefix depends
  on the layout, so even `K = 1` means holding a whole patch, which ghist does
  not do. One open-webui commit’s patch is 10 MB.
- **A second topology stream:**
  `git rev-list --default HEAD --topo-order --parents --end-of-options …` with
  the same operands produced the same hash and parent sequence as the main
  stream in all 50 repository-and-mode combinations tried, including ranges,
  paths, `-p`, and stats. It costs about two thirds of the main walk, or all of
  it with a path limit. Run concurrently, the first page’s wall time stayed
  within noise, but CPU before the first page roughly doubled (+275 ms on brew).
- **Latency:** without a commit-graph file, Git computes the whole topological
  order before emitting the first commit, so `K` more commits are almost free.
  With one, Git streams, and lookahead waits for Git to find `K` more commits.
  With a path limit that can take seconds: on homebrew-cask, the first matching
  commit for one file arrives after 66 ms, the 65th after 1.7 s.
- **Consistency:** two processes resolve revisions independently, so a commit,
  fetch, or rebase between them makes the streams disagree. Comparing each main
  record with the topology entry at the same position detects that in constant
  time per commit, and ghist would have to fail rather than fall back silently.

The Python model also swept `K` with a rule that reserves holes for lanes the
window proves will open and close inside a new lane. Crossings fell with `K` and
width rose; the knee was around `K = 32`, which removed 30–67% of first-fit’s
crossings on the large repositories at 0.4–19% more mean width. Small `K` was
not a safe partial step: at `K = 1` it drew more crossings than first-fit on
brew and ohmyzsh. A whole-history layout that sorts lanes by where they end and
polishes the result by local search removed 61–80% of crossings and every jog,
at 8–22% more mean width and 16–160 times the layout CPU, and needs the whole
topology before the first row.

ghist uses no lookahead: the gain is real, but it needs a second Git process on
every run and makes first output wait on Git in exactly the cases that are
already slow.

## Theory

The problem sits where several studied problems meet. Each maps onto part of it,
and each mapping says something about what is easy.

**Interval coloring and channel routing.** Lanes alive together need different
columns, so a layout colors an interval graph. Coloring intervals in order of
their left ends is optimal offline. In VLSI channel routing this is the
left-edge algorithm (Hashimoto and Stevens 1971), which is optimal when there
are no vertical constraints, as in a channel with terminals on one side only
(Deutsch 1976). Nesting preferences are vertical constraints. Deutsch’s doglegs
split a net across tracks to satisfy them and cost one or two contacts each;
ghist’s jogs are doglegs. Online, with intervals arriving in any order, at most
`3ω − 2` colors are needed and no algorithm does better, where `ω` is the
largest number of overlapping intervals (Kierstead and Trotter 1981, as stated
by Curbelo 2024). ghist’s lanes arrive in order of their start, so width is not
the hard part; choosing among free columns is.

**Layered drawing.** The Sugiyama framework orders vertices within layers to
reduce crossings. Crossing minimization in two layers is NP-complete (Garey and
Johnson 1983), and stays NP-hard with one layer fixed (Eades and Wormald 1994).
The barycenter and median heuristics, sifting, and exact branch-and-cut methods
all permute each layer freely and straighten edges afterwards; Brandes–Köpf
coordinate assignment bends a long edge at most twice, at its ends (Healy and
Nikolov). In a terminal, a permutation between rows is a visible jog, so each
lane keeps one column and the problem becomes track assignment instead. Online
one-sided crossing minimization in the slotted model is not competitive for any
`k ≥ 2` (Burjons, Fuchs, and Lotze 2022).

**Fixed-order arc diagrams.** With column zero as a spine and every side lane an
arc from its fork row to its join row, a column is an arc’s height. On one page
the crossings are fixed by the order of endpoints, and nested arcs must have the
inner arc lower: the two-lane table above. Choosing between two pages is the
NP-hard fixed linear crossing number problem (Masuda et al. 1990; Buchheim and
Zheng 2006), and ghist’s column-zero rule removes that choice.

**Metro lines.** Ordering metro lines along shared edges is NP-hard on
caterpillars, but polynomial when the side on which each line ends is given
(Fink and Pupyrev 2013). In ghist, every lane leaves toward the lane it joins,
so its side is given: the tractable case. Its metro-map form of the nesting rule
is that a lane about to join another should already sit next to it.

**Storylines.** Characters are curves over time that must be adjacent at
meetings; the objectives are crossings, wiggles, and white space, which are
ghist’s crossings, bends, and width. Crossing minimization is NP-complete in
general and fixed-parameter tractable in the number of characters (Kostitsyna et
al. 2015). Minimizing wiggles is NP-complete even with every order fixed (Dobler
et al. 2025). With a protagonist present at every meeting and drawn on one side,
every instance can be drawn with only unavoidable crossings, in `O(k²n)` time
(Hegemann and Wolff 2024). The protagonist is ghist’s first-parent chain in
column zero; this is the closest published model.

**Online algorithms and lookahead.** Recoloring intervals is the formal version
of moving lanes: maintaining an optimal `k`-coloring needs `Ω(k)` recolorings
per step, amortized, for small `k` (Bosek et al. 2020). Lookahead rarely changes
worst-case bounds: for online coloring of classes such as trees and bipartite
graphs, a lookahead of `O(n / log n)` does not improve the `Θ(log n)`
competitive ratio (Albers and Schraink 2017). That matches the argument above: a
bounded window helps typical histories, not the worst case. Lazy compaction is a
rent-or-buy choice in the sense of ski rental.

**Version-control graphs.** No peer-reviewed algorithm for commit-graph lanes
was found. Isaacs and Gamblin describe Git’s layout as one that “conserves
columns” and is “an unambiguous representation: when one edge is routed into
another, they both exit at the same terminus,” at the cost of many rows (Isaacs
and Gamblin 2019). Courtiel and Pépin formalize “git graphs” as a main branch
with non-interfering feature branches (Courtiel and Pépin 2024), the class for
which the two-lane table is exact.

## Prior art

Tools fall into six families. Behavior was learned from documentation, papers,
black-box output, and the source of permissively licensed tools only. GPL
implementations, including Git’s `graph.c`, tig, gitk, and Sapling, were not
read.

| Family                                   | Lane               | Needs         | Lanes move | Members                                                  |
| ---------------------------------------- | ------------------ | ------------- | ---------- | -------------------------------------------------------- |
| A. Insert at the commit, collapse left   | Shared per parent  | Nothing ahead | Constantly | `git log --graph`                                        |
| B. Sparse fixed columns, first free slot | Shared or separate | Nothing ahead | Rarely     | ghist, Sapling’s renderdag (jj)                          |
| C. One lane per edge, appended right     | One per child edge | Nothing ahead | Yes        | VS Code’s built-in graph, lazygit, SourceGit, GitX       |
| D. Straight branches, children first     | One per branch     | Children map  | Never      | pvigier’s straight branches, DoltHub, serie              |
| E. Interval scheduling of branch chains  | One per branch     | Whole window  | Never      | git-graph (shortest first), GitLab (650 commits), Fossil |
| F. Global order, rank per row            | One per edge       | Whole graph   | Yes        | IntelliJ                                                 |

- **Git** inserts a merge’s parents next to the commit and pushes every lane on
  the right outward, then slides lanes back as branches end. The newest branch
  is always innermost, so Git nests short branches without foresight and draws
  one crossing on the example above, paid for with a lateral move of the long
  lane at every merge and a graph-only row per commit.
- **jj** draws through Sapling’s renderdag: lanes stay put, a vacated column
  stays empty until reused, and horizontals run over intervening lanes. It has
  no column-zero rule.
- **Per-edge tools** give each child edge its own lane until the parent’s row.
  On the example they need width five and draw six crossings.
- **Whole-history tools** know each branch’s lifetime. git-graph assigns columns
  shortest-lived first, which draws the example with no crossings at width five.
  IntelliJ ranks lanes by a global layout index and cuts edges of 30 rows or
  more to arrows; an issue open since 2015 asks for straight lanes, in the words
  “keeping longer branches to the left, and the shorter branches to the right.”
- **Bounded windows are common:** GitLab lays out at most 650 commits, the VS
  Code Git Graph extension loads 300 and then 100 at a time, Fossil lays out a
  page.
- **Pinning the trunk** is common: serie’s primary branch, Fossil’s trunk on the
  far left, git-graph’s ordered branch groups.

No surveyed tool keeps shared, fixed lanes and also nests by lifetime. The
families that nest either move existing lanes outward (A, F) or know lifetimes
before placing lanes (D, E).

## Sources

Theory:

- Albers and Schraink, “Tight Bounds for Online Coloring of Basic Graph
  Classes,” ESA 2017. <https://arxiv.org/abs/1702.07172>
- Bosek, Disser, Feldmann, Pawlewicz, and Zych-Pawlewicz, “Recoloring Interval
  Graphs with Limited Recourse Budget,” SWAT 2020.
  <https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.17>
- Buchheim and Zheng, “Fixed Linear Crossing Minimization by Reduction to the
  Maximum Cut Problem,” COCOON 2006. <https://doi.org/10.1007/11809678_53>
- Burjons, Fuchs, and Lotze, “The Slotted Online One-Sided Crossing Minimization
  Problem on 2-Regular Graphs,” 2022. <https://arxiv.org/abs/2201.04061>
- Courtiel and Pépin, “Random Generation of Git Graphs,” GASCom 2024.
  <https://arxiv.org/abs/2403.01902>
- Curbelo, “Online coloring of short interval graphs and two-count interval
  graphs,” 2024, which states Kierstead and Trotter’s 1981 bound.
  <https://arxiv.org/abs/2412.17193>
- Deutsch, “A ‘Dogleg’ Channel Router,” DAC 1976, which cites Hashimoto and
  Stevens for the left-edge algorithm.
  <https://my.ece.utah.edu/~kalla/phy_des/doglegcr-1.pdf>
- Dobler, Hegemann, Nöllenburg, and Wolff, “Optimizing Wiggle in Storylines,”
  GD 2025. <https://arxiv.org/abs/2508.19802>
- Eades and Wormald, “Edge crossings in drawings of bipartite graphs,”
  Algorithmica 11(4), 1994.
  <https://research.monash.edu/en/publications/edge-crossings-in-drawings-of-bipartite-graphs/>
- Fink and Pupyrev, “Metro-Line Crossing Minimization: Hardness, Approximations,
  and Tractable Cases,” GD 2013. <https://arxiv.org/abs/1306.2079>
- Garey and Johnson, “Crossing Number is NP-Complete,” SIAM J. Algebraic
  Discrete Methods 4(3), 1983.
- Healy and Nikolov, “Hierarchical Drawing Algorithms,” chapter 13 of the
  Handbook of Graph Drawing and Visualization.
  <https://cs.brown.edu/people/rtamassi/gdhandbook/chapters/hierarchical.pdf>
- Hegemann and Wolff, “Storylines with a Protagonist,” GD 2024.
  <https://drops.dagstuhl.de/storage/00lipics/lipics-vol320-gd2024/LIPIcs.GD.2024.26/LIPIcs.GD.2024.26.pdf>
- Isaacs and Gamblin, “Preserving Command Line Workflow for a Package Management
  System using ASCII DAG Visualization,” IEEE TVCG 25(9), 2019.
  <https://arxiv.org/abs/1908.07544>
- Kostitsyna, Nöllenburg, Polishchuk, Schulz, and Strash, “On Minimizing
  Crossings in Storyline Visualizations,” GD 2015.
  <https://arxiv.org/abs/1509.00442>
- Masuda, Nakajima, Kashiwabara, and Fujisawa, “Crossing Minimization in Linear
  Embeddings of Graphs,” IEEE Trans. Computers 39(1), 1990.
  <https://doi.org/10.1109/12.46286>

Tools:

- Git, “history graph API.” <https://git-scm.com/docs/api-history-graph/2.19.2>
- pvigier, “Commit Graph Drawing Algorithms,” 2019.
  <https://pvigier.github.io/2019/05/06/commit-graph-drawing-algorithms.html>
- DoltHub, “Drawing a commit graph,” 2024.
  <https://www.dolthub.com/blog/2024-08-07-drawing-a-commit-graph/>
- jj’s graph log and renderdag.
  <https://github.com/jj-vcs/jj/blob/main/cli/src/graphlog.rs>,
  <https://docs.rs/sapling-renderdag/latest/renderdag/>
- git-graph’s branch assignment.
  <https://github.com/git-bahn/git-graph/blob/master/docs/branch_assignment.md>
- IntelliJ’s VCS log layout, and issue IJPL-89295.
  <https://github.com/JetBrains/intellij-community/tree/master/platform/vcs-log/graph>,
  <https://youtrack.jetbrains.com/issue/IJPL-89295>
- VS Code’s source-control history graph.
  <https://github.com/microsoft/vscode/blob/main/src/vs/workbench/contrib/scm/browser/scmHistory.ts>
- VS Code Git Graph extension settings.
  <https://github.com/mhutchie/vscode-git-graph/wiki/Extension-Settings>
- lazygit’s graph.
  <https://github.com/jesseduffield/lazygit/blob/master/pkg/gui/presentation/graph/graph.go>
- SourceGit’s commit graph.
  <https://github.com/sourcegit-scm/sourcegit/blob/master/src/Models/CommitGraph.cs>
- GitX’s graphing notes.
  <https://github.com/pieter/gitx/blob/master/Documentation/GraphingAPI.txt>
- serie’s graph calculation.
  <https://github.com/lusingander/serie/blob/master/src/graph/calc.rs>
- GitLab’s network graph.
  <https://gitlab.com/gitlab-org/gitlab-foss/-/blob/master/app/models/network/graph.rb>
- Fossil’s timeline graph. <https://fossil-scm.org/home/file/src/graph.c>