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.
4
-
$\begingroup$ Also posted on cstheory: cstheory.stackexchange.com/questions/12569/… $\endgroup$– Gregor SamsaCommented Sep 11, 2012 at 20:57
-
$\begingroup$ Are your graphs simple? 2-connected? 3-connected? $\endgroup$– Brendan McKayCommented Sep 11, 2012 at 22:03
-
$\begingroup$ This is one abstracted piece of a bigger problem of course, and at least on the surface I don't have any additional information. $\endgroup$– ArnabCommented Sep 11, 2012 at 23:31
-
$\begingroup$ 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. $\endgroup$– ArnabCommented Sep 12, 2012 at 18:07
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
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.
answered Sep 11, 2012 at 23:42
$\begingroup$
$\endgroup$
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.
answered Sep 12, 2012 at 5:38