# Cycles and faces in planar 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.

• What do you mean by "length of the face boundaries"? – draks ... Dec 16 '15 at 13:29

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

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.

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

• With "the answer is yes" do you mean that the number of $3$-gonal,$4$-gonal,$5$-gonal... faces is unique ? – Peter Sep 21 '14 at 19:43
• I think you are right with the claim that any face can be made to the outer face. – Peter Sep 21 '14 at 19:44
• @peter yes, unless I've made a mistake I guess. – Casteels Sep 21 '14 at 19:46