12.1: Drawing Graphs in the Plane
- Page ID
- 48377
Suppose there are three dog houses and three human houses, as shown in Figure 12.1. Can you find a route from each dog house to each human house such that no route crosses any other route?
A similar question comes up about a little-known animal called a quadrapus that looks like an octopus with four stretchy arms instead of eight. If five quadrapi are resting on the sea floor, as shown in Figure 12.2, can each quadrapus simultaneously shake hands with every other in such a way that no arms cross?
Both these puzzles can be understood as asking about drawing graphs in the plane. Replacing dogs and houses by nodes, the dog house puzzle can be rephrased as asking whether there is a planar drawing of the graph with six nodes and edges between each of the first three nodes and each of the second three nodes. This graph is called the complete bipartite graph \(K_{3,3}\) and is shown in Figure 12.3.(a). The quadrapi puzzle asks whether there is a planar drawing of the complete graph \(K_5\) shown in Figure 12.3.(b).
In each case, the answer is, “No —but almost!” In fact, if you remove an edge from either of these graphs, then the resulting graph can be redrawn in the plane so that no edges cross, as shown in Figure 12.4.
Planar drawings have applications in circuit layout and are helpful in displaying graphical data such as program flow charts, organizational charts, and scheduling conflicts. For these applications, the goal is to draw the graph in the plane with as few edge crossings as possible. (See the box on the following page for one such example.)
Steve Wozniak and a Planar Circuit Design
When wires are arranged on a surface, like a circuit board or microchip, crossings require troublesome three-dimensional structures. When Steve Wozniak designed the disk drive for the early Apple II computer, he struggled mightily to achieve a nearly planar design according to the following excerpt from apple2history.org which in turn quotes Fire in the Valley by Freiberger and Swaine:
For two weeks, he worked late each night to make a satisfactory design. When he was finished, he found that if he moved a connector he could cut down on feedthroughs, making the board more reliable. To make that move, however, he had to start over in his design. This time it only took twenty hours. He then saw another feedthrough that could be eliminated, and again started over on his design. “The final design was generally recognized by computer engineers as brilliant and was by engineering aesthetics beautiful. Woz later said, ’It’s something you can only do if you’re the engineer and the PC board layout person yourself. That was an artistic layout. The board has virtually no feedthroughs.’
