bijection between planar graphs and maps
- Planar graphs are graphs whose edges do not cross
- For this picture I'm imagining maps that are "nice" looking. Like the map of the United States.
1. Injective
- Take a map. You can represent it in list form by writing out its regions and the regions that share a border.
- The mapping from maps to graphs works like this: put a vertex in the middle of each region. Draw a hashmark at each border, normal to the border. On either side of this border, each hashmark can be extended to reach a vertex without leaving the region. This results in a planar graph.
- Changing which regions border what will change the list representation, which will result in a different adjacency matrix for the graph. So the mapping is injective.
2. Surjective
- Each planar graph has a corresponding planar map. To see this, imagine printing out your planar graph in very thick ink. Then, each edge can be seen, not as a line, but as a portion of a region.