Guaranteeing a path is on the outer face of a planar graph

236 Views Asked by At

Let $G$ be a planar graph containing a path $P$. Is it always possible to draw $G$ in the plane so that the path is on the outer face?

If the path consists of a single edge then one can use stereographic projection to embed $G$ onto a sphere, reorient the sphere so that $P$ is one of the edges enclosing the North pole and then project the graph back on the plane. My question is how to do a similar thing if $P$ has more than one edge.

2

There are 2 best solutions below

1
On BEST ANSWER

The answer is no. The graph $K_4-e$ provides an counterexample. Enumerate the vertices $\{1,2,3,4\}$ and take the path $(1, 2, 3, 4)$. No matter how you try to embed the edges $(1,3)$ and $(2,4)$, the edges on your path no longer share a common face.


Gilleain illustrates my idea in his answer well, but I just made this image before I saw his post, so:

k4-e

Edge $(1,2)$ is on faces $f_0$ and $f_1$, edge $(2,3)$ is on faces $f_1$ and $f_2$, and edge $(3,4)$ is on faces $f_0$ and $f_2$. It doesn't matter which of the faces you try to declare as the outer face, the edges of the path $(1,2,3,4)$ can't share a common face.

3
On

As an addendum to Mike's answer, here is an image that (I think) shows the problem he outlines:

Embedding a path from K4-e

The red line is the path (1, 2, 3, 4) and the two possible embeddings to the right show the difficulty of putting this path in the outer face.