A "planar" graph is one that may be drawn on the 2-D plane with its edges inter-
secting only at its vertices.
·
Examples include:
·
- A map of a country's adjacent states or territories.
- The layout of a maze or a city street plan.
·
An  example of the latter is the arrangement of seven bridges over a fork in the
river  at  Königsberg  (now  Kaliningrad in Western Russia). One of the earliest
achievements in graph theory was a proof in 1735 by Swiss mathematician Leonhard
Euler, that is it impossible to walk over each bridge exactly once.
·
Here  is  a  map  of  the  area,  together  with  a picture of the corresponding
graph (*) and its coding; the four areas of land adjacent to the river are cons-
idered vertices, and the bridges, edges:
·
    Map                ┐ ┌     ┐ ┌   [1]     ┐ ┌
    ---         ┌──────│ │─────│ │───────────│ │──────
                │~~~~~~│ │~~~~~│ │~~~~~~~~~~~│ │~~~~~~~
                │~~~┌──│ │─────│ │───┐~~~┌───│ │────────
                │~~~│  ┘ └     ┘ └   │~~~│   ┘ └
                │~~~│      [2]      └─────┘
                │~~~│  ┐ ┌     ┐ ┌  ┌─────┐
           ─────┘~~~└──│ │─────│ │───┘~~~│   [3]
            ~~~~~~~~~~~│ │~~~~~│ │~~~~~~~│
            ───────────│ │─────│ │───┐~~~│
                       ┘ └     ┘ └   │~~~│   ┐ ┌
                           [4]       │~~~└───│ │───────
                                     │~~~~~~~│ │~~~~~~~~
                                     └───────│ │─────────
    Graph                                    ┘ └
    -----   ┌───1───┐
            │   │   │       Coding:  (2 2 3)(1 1 3 4 4)(1 2 4)(2 2 3)
            │   │   │
            ├───2───3
            │   │   │
            │   │   │
            └───4───┘
·
Euler's  masterstroke  was  in  considering _vertices_, rather than _edges_ when
thinking about the problem. His proof went something along the lines of:
·
The number of edges issuing from a vertex is called its "degree". To succeed all
but  the starting and finishing vertices must have an even degree (corresponding
with  an entry to, and exit from the vertex). This cannot be the case in Königs-
berg, as more than two vertices have an odd degree.
·
(*) Note  that the graph above is strictly a "pseudo-" or "multi-" graph as some
vertices  are  connected  by more than one edge. This is apparent from duplicate
items in the graph coding:  {~⍵≡∪¨⍵}.
·
An example of a non-planar graph is any complete graph of size>4:
·
    {⍵∘{⍺~⍵}¨⍵}∘⍳ 5         ⍝ order ⍵ complete graph.
┌───────┬───────┬───────┬───────┬───────┐
│2 3 4 5│1 3 4 5│1 2 4 5│1 2 3 5│1 2 3 4│
└───────┴───────┴───────┴───────┴───────┘

Back to: contents

Back to: Workspaces