3
$\begingroup$

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.

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

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.)

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.