<p>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.</p>

CC BY-SA 3.0
2012-09-11T20:18:27.763Z
About your definition of "degree": is an edge that is traversed twice on a face counted twice?
Timothy Sun
CC BY-SA 3.0
2012-09-11T20:23:10.423Z
Didn't think of that possibility. But for each face, each edge bounding it, need be counted only once. right ?  Or am I missing something very obvious ?
Arnab
CC BY-SA 3.0
2012-09-11T20:24:08.707Z
Consider a planar embedding of a graph with a cut-edge. That cut-edge will always appear twice in some face-boundary walk.
Timothy Sun
CC BY-SA 3.0
2012-09-11T20:31:45.583Z
OK. Let's count each edge once.
Arnab
CC BY-SA 3.0
2012-09-11T20:37:45.427Z
At least for $d=2,3,4$, there can be arbitrarily large faces. For $d=2$, take really long cycles. For $d=3,4$, it's easier to think in the dual form, i.e., triangulations and quadrangulations with arbitrarily high degree. For example, for $d=3$, take the cone of the wheel graphs.
Timothy Sun
CC BY-SA 3.0
2012-09-11T23:36:16.837Z
For d=3,4 it's easy enough to think in the primal, geometrically: d=3 may be given by a prism over an n-gon, d=4 by an antiprism. d=5 is also possible but doesn't have quite as simple a description (e.g. one way to do it is to take an icosahedron, choose two poles interior to opposite faces, cut it on a longitude line from pole to pole, and glue multiple copies together along their cut lines).
David Eppstein
CC BY-SA 3.0
2012-09-12T00:26:12.527Z
It appears that you have [crossposted this question](http://mathoverflow.net/questions/106951/degree-of-faces-in-a-regular-graph) *simultaneously*. Our [site policy](http://meta.cstheory.stackexchange.com/a/231/) only permits a repost after sufficient time has passed and you have not obtained the desired answer elsewhere. Simultaneous crossposting duplicates effort and fractures discussion. I am voting to close;  if your question is still not answered you may request reopening by flagging the question for moderator attention (after summarizing relevant discussions from other sites).
David Eppstein
CC BY-SA 3.0
2012-09-12T17:58:07.190Z
Thanks for your answer David. I had no idea that I cannot cross-post; I did so thinking it might simply come to more attention simultaneously. Apologies.
Arnab
<graph-theory><co.combinatorics>
Degree of faces in a regular graph
Arnab
# Degree of faces in a regular graph

(Asked by: username_0 on 2012-09-11)

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.

**Tags:** graph-theory, co.combinatorics

> **Comments:**
> **username_1**: About your definition of "degree": is an edge that is traversed twice on a face counted twice?  
> **username_0**: Didn't think of that possibility. But for each face, each edge bounding it, need be counted only once. right ?  Or am I missing something very obvious ?  
> **username_1**: Consider a planar embedding of a graph with a cut-edge. That cut-edge will always appear twice in some face-boundary walk.  
> **username_0**: OK. Let's count each edge once.  
> **username_1**: At least for $d=2,3,4$, there can be arbitrarily large faces. For $d=2$, take really long cycles. For $d=3,4$, it's easier to think in the dual form, i.e., triangulations and quadrangulations with arbitrarily high degree. For example, for $d=3$, take the cone of the wheel graphs.  
> **username_2**: For d=3,4 it's easy enough to think in the primal, geometrically: d=3 may be given by a prism over an n-gon, d=4 by an antiprism. d=5 is also possible but doesn't have quite as simple a description (e.g. one way to do it is to take an icosahedron, choose two poles interior to opposite faces, cut it on a longitude line from pole to pole, and glue multiple copies together along their cut lines).  
> **username_2**: It appears that you have [crossposted this question](http://mathoverflow.net/questions/106951/degree-of-faces-in-a-regular-graph) *simultaneously*. Our [site policy](http://meta.cstheory.stackexchange.com/a/231/) only permits a repost after sufficient time has passed and you have not obtained the desired answer elsewhere. Simultaneous crossposting duplicates effort and fractures discussion. I am voting to close;  if your question is still not answered you may request reopening by flagging the question for moderator attention (after summarizing relevant discussions from other sites).  
> **username_0**: Thanks for your answer David. I had no idea that I cannot cross-post; I did so thinking it might simply come to more attention simultaneously. Apologies.  

---

## 0 answers

