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$
1
  • $\begingroup$ What do you mean by "length of the face boundaries"? $\endgroup$
    – draks ...
    Commented Dec 16, 2015 at 13:29

1 Answer 1

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .