UP | HOME

bijection between planar graphs and maps

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.

Created: 2025-11-02 Sun 18:55