A plane is a colour

The previous essay ends with a graph — an object of the same kind the topology field builds, measured rather than given: one node per link, one edge per pair that may not share a plane, half of the edges read off the mechanism’s own chain and half measured over its drive.

The obvious question to ask a graph like that is how few colours it takes, and the obvious answer is that this is a graph colouring, which is a problem with a name, a literature and a hundred implementations. Most of that is right. The part that is not right is the part this essay is about, and it does not change the count — it changes which of the answers can be built.

Exactly, not greedily #

The fewest planes is computed by backtracking rather than by a greedy colouring, and the reason is that the answer is a claim.

This mechanism needs three planes is false if two will do, and a greedy colouring only ever gives an upper bound. The standard greedy — DSATUR, which repeatedly colours the vertex with the most differently-coloured neighbours — is good and is not exact: its answer depends on how ties are broken, which depends on the order the links happen to be listed in, which on this site is the order somebody typed them.

So the search is exhaustive over assignments, smallest number of planes first, with the usual symmetry breaking: vertex k may use at most one colour beyond those already used, because a colouring is invariant under permuting its colours and searching all the permutations is searching one answer many times. On eight links that is a few thousand nodes and it finishes instantly.

The two are reported side by side in the table, and on this catalogue they agree everywhere — greedy never needs more than the exact answer on any of the nine machines. That is a small and useful fact: it says these graphs are easy, being sparse and small, and that a designer using the obvious method will not be led astray on machines of this size. It is reported because agreement measured is worth more than agreement assumed, and because the first machine where they differ will be visible.

What the counts are #

Nine machines, ninety solved positions each:

The four-bars need three — four joined pairs round the ring, plus the crank and rocker overlapping across it. Peaucellier’s cell, eight links and fourteen joined pairs, needs four. The slider crank needs three. Chebyshev’s linkage, whose long arms cross on the page and never in fact, needs two, and so do the two machines whose only conflicts are against something bolted to the frame.

Two is the floor and nothing reaches one, on machines whose mobility is one and whose motion is entirely planar, which is worth stating as a result rather than as an aside: no mechanism with a moving joint fits in a plane, because the two links at that joint both surround the pin. The floor is structural and the interesting variation is above it.

Where the third plane comes from #

The four-bar’s answer is worth taking apart, because it is the one a reader can check by hand and the one whose extra plane is easy to miss.

Four links pinned in a ring give a four-cycle in the conflict graph: crank–coupler, coupler–rocker, rocker–frame, frame–crank. A four-cycle is two-colourable, by alternating round it — crank and rocker in one plane, coupler and frame in the other. Every joined pair is resolved, every pin joins adjacent planes, and the answer would be two.

The measured conflict breaks it. The crank and the rocker overlap somewhere on the turn, and they are the two links the alternating scheme puts together. Adding that one edge makes the graph a four-cycle with a diagonal, which is not two-colourable, and the answer becomes three.

So the third plane is bought by a measurement rather than by the structure, and a designer working from the chain alone would not know it was needed. It is also dimension-dependent: shorten the crank enough that it never reaches the rocker’s territory and the edge disappears, and the machine goes back to two planes. Chebyshev’s linkage is the catalogue’s example of a four-bar for which that is already true.

And then the pins have to get through #

Here is the part that is not a colouring.

A pin joining a link in plane 1 to a link in plane 3 has to pass through plane 2 on the way. Anything sitting in plane 2 whose material covers that pin’s position — at any configuration of the drive — is pierced by it. The link would have to have a hole in it, and a hole in a link is a different part.

That is a condition on three links at once: the two the pin joins, and the one in between. A colouring’s conditions are on two at a time, and no amount of adding edges can express it, because the condition is not these two must differ but this one must not be between those two.

Betweenness is not preserved by permuting colours, which is what makes this genuinely outside the colouring problem rather than a variant of it. Swap the names of planes 1 and 2 and a proper colouring stays proper; the same swap turns a link that was above a pin into a link that is inside it.

That has a practical consequence in the code, and it cost this field its second real bug. The layer search reused the colouring search’s symmetry breaking — vertex k may use at most one colour beyond those already used — which is valid for a colouring and invalid here, and with it in place the program reported that a four-bar cannot be built out of solid material in any number of planes. A result that absurd is easy to catch. A subtler version of the same mistake, on a machine where the answer merely comes out one plane too many, would not have been.

What it costs, counted #

The condition does not change the number of planes on any machine in this catalogue. What it removes is arrangements, and those are counted rather than argued about.

Enumerate every assignment of three planes to a crank rocker’s four links. Six are proper colourings of its conflict graph. Of those six, two let every pin through and four put a pin through a link.

Peaucellier’s cell, at four planes: 192 proper colourings, of which 96 are buildable. Watt’s linkage: six proper, four buildable. The slider crank: six proper, four buildable.

So the ordering condition removes between a third and two thirds of the answers a colouring would accept, on every machine that has any pierced pins at all. A designer who colours the graph and picks the first answer that comes out has a two-in-three chance of a machine whose pin goes through a link, and no gate anywhere on this site would notice, because the colouring is proper and every link is in a plane of its own from every link it conflicts with.

Which pins are at risk #

A pin is only at risk if something covers it, and covers is a measured property: at some configuration of the drive, a link not attached to that pin has material over its position.

On a four-bar there are two such pins. The crank pin at the frame is passed over by the coupler — which is the same fact that makes the coupler cross its own driving pivot, read at a different scale — and the rocker pin is passed over by the crank on part of the turn. On Peaucellier’s cell there is one.

The measurement is the same sweep everything else in this field uses, with a point-in-polygon test instead of a distance: at each position, for each joint, is that joint’s position inside any link’s material other than the links it belongs to. It is cheap, it is discrete, and it inherits the sampling question of the certificate essay in a milder form — a pin that is covered for only a sliver of the drive can be missed, and the consequence of missing it is an assignment that is accepted and should not be.

The condition, stated once #

A layer assignment is a map from links to planes 1…k such that:

1. no two conflicting links share a plane — the colouring condition; and
2. for every joint, and every link covering that joint’s position at some configuration, that link’s plane is not strictly between the planes of any two links the joint connects.

The search is a brute-force walk over assignments with the colouring condition pruned as it goes and the pin condition checked at the leaves. The counts are small — nine machines, at most eight links, at most four planes — and the alternative is a heuristic whose answer would have to be believed.

What it does not model #

Three things, each of which would make the condition harder and none of which changes the shape of the argument.

A stepped pin. A real shaft — the sort a clearance is measured on — can be turned down: fat where it carries a bearing, thin where it passes a link, so that a link “in the way” clears the thin section. That relaxes condition 2 into a statement about diameters rather than about betweenness, and it is exactly the sort of thing a machinist does to rescue an arrangement this model calls impossible.

A link with a hole in it. Also common, also a real fix, and it makes the covering test a question about the part’s actual outline rather than its convex outline — which the decomposition could support and this field does not use.

A pin that stops short. A joint between two links in planes 1 and 2 does not need a shaft reaching plane 3, and the model already knows that: the condition is only ever about planes strictly between the two the pin joins. What it does not model is a blind pin — one pressed into a link and reaching only part way — which is another real fix and another relaxation of the same condition.

Plate thickness. Every plane here is an index, not a height. Two links in adjacent planes are in different plates and that is all that is said; how thick a plate is, how much running clearance goes between them, and how long the pin therefore has to be are quantities this field does not carry — except in the scissor stack, where the stowed height is the whole question and is put in by hand.

What a plane costs, so the count means something #

The number of planes is not free, and it is worth saying what it buys and what it costs so that “three rather than two” is a statement about a machine rather than about a graph.

Each extra plane adds a plate thickness plus a running clearance to the depth of the machine, which is what makes a scissor’s two planes the reason it is the mechanism people stow — and it adds it to the pin, which now has to span further. A pin spanning three plates is a longer cantilever than one spanning two, and everything about how it is supported gets harder. This site does not compute any of that, because all of it is force, but the geometric half is real and countable: the stack is deeper, the pins are longer, and the parts are further from each other.

There is a second cost that is purely geometric and this field can state. Links in different planes cannot be pinned by a simple pin at a joint they do not both touch. In the two-plane arrangement of an idealised four-bar every pin joins adjacent plates; in the three-plane one, the pin at the crank-to-frame joint may have to reach from plane 1 to plane 3, and it is exactly those long pins that the ordering condition is about. So the extra plane and the pierced pins are the same phenomenon read twice: adding planes separates the links and spreads the pins, and spreading the pins is what puts them through things.

Why the number is not the interesting part #

It would be easy to read this essay as being about a count, and the count is the least of it.

Three planes for a four-bar is a fact a competent designer knows without computing anything, in the sense that they would draw the crank on the outside, the coupler in the middle and the rocker on the far side and never think about it again. What the machinery adds is not the number but the checkability: given a mechanism, a set of shapes and a drive, there is now a procedure that says whether an arrangement works, and a procedure that finds one.

And it adds the census. Six colourings, two of them buildable is not something anybody knows by feel, and it is the number that says how much of the design freedom is real. A designer who believes they have six arrangements to choose from has four times as much freedom as they actually have, and the four that do not work fail in a way that shows up when the pin is fitted rather than when the drawing is checked.

Reading a census as a design budget #

There is a way of using the census that is more useful than treating it as a curiosity, and it comes from noticing what the buildable arrangements have in common.

On the crank rocker the two buildable arrangements are mirror images: the coupler outermost with the frame innermost, or the reverse. Both put the coupler and the frame at the two ends of the stack and the crank and rocker between them — which is exactly what makes the pins short, since the two links that pass over other links’ pins are the ones with nothing above or below them.

That is a rule of thumb falling out of an enumeration rather than being asserted: put the links that sweep over other joints at the outside of the stack. It is not a theorem, it is a property of these graphs, and it is the kind of thing a census can suggest and a colouring cannot, because the colouring throws away the ordering that the observation is about.

On Peaucellier’s cell the ninety-six buildable arrangements are more varied, and the reason is that its one pierced pin constrains only a handful of the assignments. The general pattern holds: the fraction lost is decided by how many pins are covered and by how spread out the assignment forces them to be, and both of those are measurements rather than structure.

The shape of the answer, again #

This site has met this shape before, twice, and it is worth naming.

The topology field counts kinematic chains and finds that a count of graphs admits eight for every one that deserves it, because most graphs are not mechanisms. The synthesis field finds 1,176 exactly correct three-position syntheses of which 176 are usable, because most exact answers have a defect the construction cannot see.

Here it is again, at a smaller scale and about a different object: an enumeration produces a set of candidates, a condition that the enumeration cannot express removes most of them, and the condition is only visible from outside the formalism that generated the candidates. Three times in three fields is a pattern rather than a coincidence, and the moral each time is the same. The formalism that generates the answers is not the formalism that judges them, and a site that only ever runs the first one will publish a count that is much too large and be entirely consistent about it.