Degree of faces in a regular graph

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.

-
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

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:

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.

-

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.

-