4
$\begingroup$

I've been having trouble wrapping my head around this concept. How do I calculate the degree of a face in planar graphs. In our textbook, we are given this image: A planar graph

where $f_1, f_2, f_3, f_4$ are the faces.

In the textbook, it gives the degrees of the four faces as $$deg(f_1) = 6$$ $$deg(f_2) = 3$$ $$deg(f_3) = 5$$ $$deg(f_4) = 14$$

I don't understand how they got 6 for $f_1$ and 14 for $f_4$. I know this is a very simple question, but I'm just not getting it for some reason. I would appreciate the help.

Thanks

$\endgroup$
  • $\begingroup$ You need to count both sides of every edge, in some face or other. If the leaf node inside $f_1$ had instead been mapped into $f_4$, the degrees of those two faces would have changed by $-2$ and $+2$ respectively. $\endgroup$ – Joffan Jul 27 '16 at 16:08
6
$\begingroup$

Think of the edges as being two sided. As you move around the face of $f_1$ you see both sides of the leaf edge, so that edge is counted twice. Likewise, when you travel around the outer face you see the bridge edge twice (both sides of it) so it is counted twice. Hope this helps.

$\endgroup$
  • $\begingroup$ Thank You for the reply. Just to clarify, you're saying that for each face, I have to count the number of edges, counting the bridges twice (where a bridge is an edge that, if it were removed, would split the graph into components)? $\endgroup$ – The_Questioner Jul 27 '16 at 16:11
  • $\begingroup$ @The_Questioner, that is probably a correct way to view it. I just pick a vertex, start walking around the closed walk that encloses the face and count an edge for each step. When you do this, you step out to the leaf, and then back, so it is counted twice. You traverse the bridge edge twice. $\endgroup$ – TravisJ Jul 27 '16 at 16:16
  • 1
    $\begingroup$ @The_Questioner, for example, label the vertices touching $f_1$ as N, E, S, W and f (north, east, south, west and the central f vertex). The walk that encloses the face could go: N-E-f-E-S-W-N. That walk hits the edge E-f twice, E-f and f-E. $\endgroup$ – TravisJ Jul 27 '16 at 16:18

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.