SAMS Subject Classification Number: 6

The face-degree of a face in a plane graph is the length of the walk bounding it. A plane graph is \(k\)-face-degree-regular if every face has face-degree \(k\). The well-known degree-diameter problem asks for the maximum order \(n(\Delta, D)\) of a graph with maximum degree \(\Delta\) and diameter \(D\) (for an excellent and detailed survey, see [1]). In this talk, we discuss the degree-diameter problem for (face-degree-regular) plane graphs. In particular, we focus on the results of [2] — in which the degree diameter problem for \(2D\)-face-degree-regular and \((2D+1)\)-face-degree-regular plane graphs is solved.

On the path to solving this case of the degree diameter problem, we also explore the relationship between girth, face-degree and diameter in plane graphs with small diameter and large face-degrees.

[1] M. Miller, J. Širáň, Moore graphs and beyond: A survey of the degree/diameter problem, Electron. J. Combin. 20(2) (2013), #DS14v2.

[2] B. Du Preez, Plane graphs with large faces and small diameter, Australasian J. Combin. 80(3) (2021), 401–418.