Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is there any known result on the maximum degree of faces in regular-and-planar graphs ? In particular, is anything known about maximum degree of the faces in a 4-regular planar graph? By degree of a face I mean the number of edges forming it.

share|improve this question
    
Also posted on cstheory: cstheory.stackexchange.com/questions/12569/… –  Gregor Samsa Sep 11 '12 at 20:57
    
Are your graphs simple? 2-connected? 3-connected? –  Brendan McKay Sep 11 '12 at 22:03
    
This is one abstracted piece of a bigger problem of course, and at least on the surface I don't have any additional information. –  Arnab Sep 11 '12 at 23:31
    
Thanks much to both of you, Brendan, and Joseph. I understand that it is difficult to say much without the additional information such as connectivity. However, in the same vein, I am thinking it might be possible say a bit more than what's observed here; say, for instance, the number of faces with unbounded degree has an upper bound, or something like that. –  Arnab Sep 12 '12 at 18:07
add comment

2 Answers

This will likely only serve to sharpen your question, but I will just observe that there is no upper bound on the number of edges of a face of a 4-regular planar graph:
          Regular-4 Large Face
The octagon vertices each have two incident blue and two incident red edges, and so are nodes of degree 4. The red arcs cross in nodes of degree 4. So the graph is 4-regular. Clearly the central octagon could be any even-$n$ polygon.

share|improve this answer
add comment

It makes a huge difference what restrictions are imposed. Without any restriction on connectivity or edge type, you can put every edge on a single face (a path of double edges with a loop at each end). With 2-connectivity imposed, you can get half the edges (a cycle of double edges). If you want 3-connected graphs, the antiprism (shown in Joseph's picture) gets you half the vertices and I think that is optimal when the number of vertices is even.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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