Browsing by Author "Du Preez, Brandon"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Open Access
    Distances in planar graphs
    (2021) Du Preez, Brandon; Erwin, David
    In graph theory, the degree diameter problem asks for the maximum number of vertices a graph with given maximum degree and diameter can have. The face-degree of a face in plane graph is the length of the shortest closed walk traversing the boundary of the face. A plane graph is ρ-face-degree regular if every face has face-degree ρ. This thesis begins with a literature review outlining the results and methods of papers studying planar graphs, particularly those solving the degree diameter problem for various kinds of ρ-facedegree regular graphs. In this review, we provide a correction to an error in The degree/diameter problem in maximal planar bipartite graphs by Dalf´o, Huemer and Salas. We investigate plane graphs in which the minimum face-degree is large compared to the graph's diameter, obtain a sharp upper bound for minimum face-degree in terms of diameter, and characterise the extremal graphs for this bound. We demonstrate that if a plane graph has sufficiently large minimum face degree, then it has equally large girth. We use this result to characterise planar generalised polygons (bipartite graphs whose girth is twice their diameter), and solve the degree diameter problem for plane graphs with diameter D that are 2D-face-degree regular. We solve the degree diameter problem for 2-connected, 5-face-degree regular graphs of diameter 3, and demonstrate that if the maximum degree of such a graph is sufficiently large, then the graph necessarily has girth 4. We briefly investigate the distance and connectivity properties of maximal planar graphs. We show there are no non-trivial restrictions on the radius and diameter of a maximal planar graph, give an elementary proof of the well known characterisation of minimal separators in maximal planar graphs, characterise non-separating sets of these graphs, and demonstrate that the centre of a maximal planar graph may have arbitrarily many components. We then study centres of planar and maximal planar graphs in greater depth, and characterise maximal planar graphs that are centres of planar graphs. This characterisation depends upon a new concept we introduce, which is a generalisation of eccentricity, called quasi-eccentricity. We conclude with a list of ideas for further research, open questions and conjectures.