[Math] Cycles and faces in planar graphs

graph theoryplanar-graphs

Let G be a connected planar graph. Supopose, we know all cycles of G.

  • Is this enough to determine the length of the face boundaries ?

  • In particular, are the lengths of the face boundaries unique (independent
    from the concrete embedding) ?

  • How can the length of the outer face be calculated ?

    I know Eulers formula and that a maximal planar graph with $n$ vertices has
    $3n-6$ edges and all the faces are triangles. The sum of the boundary lengths
    must be twice the number of edges.

Best Answer

The answer to all your questions is no, in general. Simple example:

enter image description here

Here the left picture has one $5$-cycle face and three $3$-cycle faces, while the right picture has two $3$-cyle faces and two $4$-cycle faces. Both outer faces are of different lengths.

But all is not lost. The issue with the above example is that the graph is only $2$-connected. If a planar graph is $3$-connected, then the answer to your first two questions are yes! Very roughly speaking (see Diestel's book for the gory details), when $G$ is a planar $3$-connected graph, then the cycles that are faces (facial cycles) are exactly those induced cycles whose deletion does not disconnect $G$. Since this is a purely graph-theoretical property of the cycles, it implies affirmative answers to your first two questions.

I seem to recall a result stating that you can choose any facial cycle to be the outer face, so I think the answer to your third question is always no unless all faces have the same length, but I can't find a reference, and so I might be misremembering something. In any case, you can find a counterexample pretty easily: Here are two embeddings of a $3$-connected graph, but with different lengths of the outer cycle. Note that they both have two $5$-cycle faces and five $4$-cycle faces however.

enter image description here

(PS sorry about the childish-ly drawn pictures.)

Related Question