# 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"? Commented Dec 16, 2015 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 ? Commented Sep 21, 2014 at 19:43
• I think you are right with the claim that any face can be made to the outer face. Commented Sep 21, 2014 at 19:44
• @peter yes, unless I've made a mistake I guess. Commented Sep 21, 2014 at 19:46