Can every planar graph be represented as a set of regions on the grid

Question

Given a planar graph, can you draw a set of connected regions on a grid such that two cells are adjacent if they touch vertically or horizontally, and two regions $A,B$ are adjacent if $A$ has a cell $a$ that is adjacent to a cell $b\in B$. The converse is clearly true. Here is a planar graph:

Here is the grid representation of the graph:

The grid drawing can obviously be much smaller. So my question is can every planar graph be represented in such a way?

Answer 1

If the entire grid must be filled

In an entirely filled rectangular grid, you will not be able to draw connected regions $\{1,2,3,4,5\}$ with adjacencies $(1,2), (2,3), (3,4), (4,5), (5,1)$. (That is, the cycle graph $C_5$.)

This configuration is easy to draw with regions that are not grid-aligned; however, it cannot be done without creating a point where all five regions meet. Such a point cannot exist in the grid: all points in the grid are adjacent to at most four cells, which are part of at most four regions.

To carry out the same argument more carefully, let's look closely at the boundary of region $1$ in a hypothetical grid drawing. This boundary is made up of segments that are edges between cells of the grid. Some of those edges are borders with region $2$, some of those edges are borders with region $5$, and some might be boundaries of the grid. We can consider several cases:

• Suppose a border with region $2$ meets a border with region $5$ at a point. Around that point, there are $4$ square cells (from region $1$, region $2$, region $5$, and some region that is either one of these or a fourth region). The adjacencies between those square cells create either a $C_3$ or $C_4$ subgraph in the graph, which does not exist in the graph we're trying to draw.
• Suppose this doesn't happen: either because region $1$ touches the side of the grid in two places separating $2$ from $5$, or because region $2$ is entirely on the inside and region $5$ entirely on the outside, or vice versa. This means that there is no way to get from region $2$ to region $5$ without going through region $1$. But that's also not true of the graph we're trying to draw, where we can go from $2$ to $5$ via $3$ and $4$.

Either way, we get a contradiction, so a drawing of $C_5$ in the grid does not exist.

If we can leave holes in the grid

This problem is resolved if you are allowed to leave some blank space in the grid which is not part of any region. In this case, any planar graph can be represented.

Here's just an intuitive argument. Take any actual pixel drawing of the graph, such as the one in the question:

To each vertex, assign the region consisting of the black pixels representing that vertex and extending halfway along each edge. Leave the white space unfilled.