�� �� ......�� ���� �� ��� �� ��� �� ��� ��� �� � � ���� ...........................................................................� � �� �� ��� �� �� �� � � ���� � �� �� � � � �� �� � � � ���� � � ������ � � � �. ......................................................................................................��Chapter 12 Planar Graphs 12.1 Drawing Graphs in the Plane Here are three dogs and three houses. ���� ���� ���� Dog Dog Dog Can you find a path from each dog to each house such that no two paths inter-sect? A quadapus is a little-known animal similar to an octopus, but with four arms. Here are five quadapi resting on the seafloor: ��������...........................................................................................������ .........................................................������ ...............................................................................................������ .........................................................����������.....................................................................................................233 .....................................................................................................� � � �� � �� �� � �� ��� � � � � �� � ���� � ��� � �� ��234 CHAPTER 12. PLANAR GRAPHS Can each quadapus simultaneously shake hands with every other in such a way that no arms cross? Informally, a planar graph is a graph that can be drawn in the plane so that no edges cross, as in a map of showing the borders of countries or states. Thus, these two puzzles are asking whether the graphs below are planar; that is, whether they can be redrawn so that no edges cross. The first graph is called the complete bipartite graph, K3,3, and the second is K5. �� ��� � � � ���������� ������� �� � � ��� ���������� ����� ���� �� ���� � ���������� �� ���� �������� ������ In each case, the answer is, “No— but almost!” In fact, each drawing would be possible if any single edge were removed. Planar graphs have applications in circuit layout and are helpful in display-ing graphical data, for example, program flow charts, organizational charts, and scheduling conflicts. We will treat them as a recursive data type and use structural induction to establish their basic properties. Then we’ll be able to describe a simple recursive procedure to color any planar graph with five colors, and also prove that there is no uniform way to place n satellites around the globe unless n = 4, 6, 8, 12, or 20.235 12.2. CONTINUOUS & DISCRETE FACES 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 mightly to achieve a nearly planar design: 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 en-gineering 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.’”a aFrom apple2history.org which in turn quotes Fire in the Valley by Freiberger and Swaine. 12.2 Continuous & Discrete Faces Planar graphs are graphs that can be drawn in the plane —like familiar maps of countries or states. “Drawing” the graph means that each vertex of the graph corresponds to a distinct point in the plane, and if two vertices are adjacent, their vertices are connected by a smooth, non-self-intersecting curve. None of the curves may “cross” —the only points that may appear on more than one curve are the vertex points. These curves are the boundaries of connected regions of the plane called the continuous faces of the drawing. For example, the drawing in Figure 12.1 has four continuous faces. Face IV, which extends off to infinity in all directions, is called the outside face. This definition of planar graphs is perfectly precise, but completely unsatis-fying: it invokes smooth curves and continuous regions of the plane to define a property of a discrete data type. So the first thing we’d like to find is a discrete data type that represents planar drawings. The clue to how to do this is to notice that the vertices along the boundary of each of the faces in Figure 12.1 form a simple cycle. For example, labeling the vertices as in Figure 12.2, the simple cycles for the face boundaries are abca abda bcdb acda. Since every edge in the drawing appears on the boundaries of exactly two contin-uous faces, every edge of the simple graph appears on exactly two of the simple cycles. Vertices around the boundaries of states and countries in an ordinary map are236 CHAPTER 12. PLANAR GRAPHS Figure 12.1: A Planar Drawing with Four Faces. IVIIIIIabcdFigure 12.2: The Drawing with Labelled Vertices. always simple cycles, but oceans are slightly messier. The ocean boundary is the set of all boundaries of islands and continents in the ocean; it is a set of simple cycles (this can happen for countries too —like Bangladesh). But this happens because islands (and the two parts of Bangladesh) are not connected to each other. So we can dispose of this complication by treating each connected component separately. But general planar graphs, even when they are connected, may be a bit more complicated than maps. For example a planar graph may have a “bridge,” as in Figure 12.3. Now the cycle around the outer face is
View Full Document
Unlocking...