Knuth–Plass Line-Breaking Algorithm

Choose a paragraph's line breaks globally by scoring feasible paths through boxes, flexible glue, and penalties instead of committing one line at a time.

Version

v4 · 2026-09-19 · History

Domain-specific #

2142

Domain group

Arts & Aesthetic Practice

Origin domain

Art & Aesthetics

Subdomains

Typesetting, Paragraph Composition → Art & Aesthetics

Aliases

Knuth-Plass line-breaking algorithm, Knuth–Plass algorithm, Knuth-Plass algorithm

Core Idea

The Knuth–Plass line-breaking algorithm chooses the breaks for a paragraph as one globally scored sequence rather than filling and committing one line at a time. Donald E. Knuth and Michael F. Plass introduced it in 1981 to let the appearance of a current line depend on consequences later in the paragraph. Its defining object language consists of boxes, glue, and penalties: fixed-width boxes hold material that the breaker treats as indivisible; glue has a natural width plus declared stretch and shrink; and penalties encode discretionary, discouraged, encouraged, inhibited, or forced breaks, including any width inserted only when a break is taken.

How would you explain it like I'm…

Whole-Paragraph Line Planner

When a book prints a story, it has to decide where each line ends. The easy way fills one line, then the next, and sometimes a later line ends up looking stretched and ugly. This method looks at the whole paragraph together and picks the line endings that make all the lines look nicest overall.

Stretchy Spaces, Best Breaks

The Knuth–Plass line-breaking algorithm decides where to end the lines of a paragraph. Words are treated like solid blocks, and the spaces between them are like springs that can stretch or squeeze a bit. Every possible line gets a 'badness' score for how much its springs had to stretch or squeeze, and some places to break, like in the middle of a word with a hyphen, get extra penalty points. Instead of choosing one line at a time, the computer compares whole-paragraph choices and picks the one with the lowest total score. That's why an early line might be set a little differently to help a later line look better.

Global Demerit Line Breaking

Knuth and Plass introduced this algorithm in 1981 to choose all of a paragraph's line breaks together as one globally scored sequence. Text is modeled as boxes (fixed-width material), glue (spaces with a natural width plus stretch and shrink), and penalties (places where breaking is encouraged, discouraged, forbidden, or forced). For each candidate line, an adjustment ratio measures how much the glue must stretch or shrink to fill the width. That ratio gives a badness score. Badness, the break's penalty, and extra charges, such as for two hyphenated lines in a row, combine into 'demerits.' Dynamic programming then finds the sequence of breaks with the least total demerits. Unlike greedy line filling, a choice on one line can depend on what happens later. The result is 'optimal' only by these defined rules, not by some universal standard of beauty.

 

The Knuth–Plass algorithm (Knuth and Plass, 1981) selects a paragraph's line breaks as a globally scored path. Its input is a stream of boxes (indivisible widths), glue (natural width plus stretch and shrink), and penalties (break costs, including widths like hyphens inserted only if the break is taken). Breaks may occur at glue after a non-discardable item or at permitted penalties; in TeX82, positive penalties discourage, negative encourage, +10000 inhibits, and −10000 forces. For a candidate line, the adjustment ratio r is (L − N)/Y when stretching or (L − N)/Z when shrinking, and TeX-style badness is about 100|r|³; overshrinking is infeasible and excessive stretch is limited by a tolerance. Badness, the break penalty, a line penalty, and cross-line charges (incompatible fitness classes, consecutive hyphenated breaks) yield demerits. Breakpoints form an acyclic network; dynamic programming sweeps left to right, keeping the best predecessor per relevant state (e.g., line number, previous fitness class) and pruning dominated options, then backtracks to the least-demerit path. TeX82 is the reference implementation, adding passes with hyphenation and emergency fallbacks. The optimum is relative to the supplied costs and rules, and the typographic roles are what distinguish it from generic optimization.

Scope of Application

The algorithm lives within digital typography and document layout wherever a whole paragraph can be represented by ordered break opportunities and scored line fits. Its uses are literal repetitions of the same mechanism, not analogies.

TeX and TeX-family paragraph composition. TeX82 provides the authoritative active-list implementation: construct or augment the horizontal list, test feasible breaks, retain least-demerit states, recover the path, and package the resulting lines.

Clarity

Knuth–Plass clarifies paragraph composition by separating opportunity, selection, and realization. A Unicode or language-specific rule can say where a break is legal; a hyphenator can add discretionary interior-word opportunities; the line breaker chooses among those opportunities; and a line packer realizes the selected lines. Treating all four as “wrapping” hides which stage caused a failure.

Manages Complexity

With \(n\) candidate breaks, brute-force enumeration can face exponentially many breakpoint subsets. The ordered network replaces combinations with subproblems: “what is the least demerit way to arrive at this future-relevant state?” If two partial layouts reach the same state, only the cheaper one can improve any continuation under the declared recurrence. This is the principle of optimality in typographic form.

Abstract Reasoning

Greedy-failure prediction. If taking the fullest current line leaves one very short successor or forces a costly hyphen, a global method can prefer an earlier break. Compare complete path demerits rather than current-line slack.

Penalty intervention. Raising a discretionary hyphen penalty should reduce its use when feasible alternatives exist; lowering it should admit hyphenation to relieve spacing. If output does not respond, inspect whether that breakpoint was generated and whether another cost dominates.

Knowledge Transfer

Within typography, the mechanism transfers intact. A book compositor, a journal engine, a narrow-column formatter, and a shaped-paragraph experiment can all use the same recognition test: ordered boxes, flexible glue, legal penalty breaks, line widths, demerits, active states, and a recovered global path. Their fonts and cost parameters differ, but failures are diagnosed through the same roles.

Relationships to Other Abstractions

Current abstraction Knuth–Plass Line-Breaking Algorithm Domain-specific

Parents (2) — outgoing typed relations

• Knuth–Plass Line-Breaking Algorithm is a kind of Algorithm Prime

  prime:algorithm — proposed strict subsumption parent. For a finite paragraph and fixed parameter contract, it is a definite terminating procedure with admissible input, effective steps, a breakpoint/line output, and correctness relative.

• Knuth–Plass Line-Breaking Algorithm is a kind of Dynamic Programming Prime

  prime:dynamic_programming — proposed strict subsumption parent. Knuth–Plass is dynamic programming specialized to ordered typographic breakpoint states.

Hierarchy paths (4) — routes to 4 parentless roots

• Knuth–Plass Line-Breaking Algorithm → is a kind of Algorithm → presupposes, conditional Function (Mapping)

Show alternative paths (3)

Neighborhood in Abstraction Space

Knuth–Plass Line-Breaking Algorithm sits in a sparse region of the domain-specific corpus (81^st percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

• Wave Picking — 0.82
• Metrical Bridge — 0.82
• Engineering Critical Assessment — 0.81
• Poetic Metre — 0.81
• Acrostic — 0.81

Computed from structural-signature embeddings · 2026-10-25