Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Distances in planar graphs
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...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
Department of Mathematics and Applied Mathematics
2022
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613148277637120 |
|---|---|
| access_status_str | Open Access |
| author | Du Preez, Brandon |
| author2 | Erwin, David |
| author_browse | Du Preez, Brandon Erwin, David |
| author_facet | Erwin, David Du Preez, Brandon |
| author_sort | Du Preez, Brandon |
| collection | Thesis |
| description | 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. |
| format | Thesis |
| id | oai:open.uct.ac.za:11427/35717 |
| institution | University of Cape Town (South Africa) |
| language | eng |
| last_indexed | 2026-06-10T12:31:31.816Z |
| license_str | Not specified — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from UCTD — University of Cape Town Open Access Repository |
| publishDate | 2022 |
| publishDateRange | 2022 |
| publishDateSort | 2022 |
| publisher | Department of Mathematics and Applied Mathematics |
| publisherStr | Department of Mathematics and Applied Mathematics |
| record_format | dspace |
| source_str | UCTD — University of Cape Town Open Access Repository |
| spelling | oai:open.uct.ac.za:11427/35717 Distances in planar graphs Du Preez, Brandon Erwin, David Mathematics and Applied Mathematics 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. 2022-02-18T06:09:46Z 2022-02-18T06:09:46Z 2021 2022-02-10T09:07:17Z Doctoral Thesis Doctoral PhD http://hdl.handle.net/11427/35717 eng application/pdf Department of Mathematics and Applied Mathematics Faculty of Science |
| spellingShingle | Mathematics and Applied Mathematics Du Preez, Brandon Distances in planar graphs |
| thesis_degree_str | Doctoral |
| title | Distances in planar graphs |
| title_full | Distances in planar graphs |
| title_fullStr | Distances in planar graphs |
| title_full_unstemmed | Distances in planar graphs |
| title_short | Distances in planar graphs |
| title_sort | distances in planar graphs |
| topic | Mathematics and Applied Mathematics |
| url | http://hdl.handle.net/11427/35717 |
| work_keys_str_mv | AT dupreezbrandon distancesinplanargraphs |