G-angulability of convex geometric graphs
In this thesis, we consider the g-angulation existence problem of a convex geometric graph G. A triangulation on n points in convex position is a plane graph on the convex hull in which each face is a triangle except the exterior face. A g-angulation on n points in convex position is a plane graph i...
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
2018
|
| Subjects: | |
| Online Access: | http://psasir.upm.edu.my/id/eprint/76823/1/FS%202018%2077%20-%20IR.pdf |
| _version_ | 1825950733629915136 |
|---|---|
| author | al-Hakeem, Niran Abbas Ali |
| author_facet | al-Hakeem, Niran Abbas Ali |
| author_sort | al-Hakeem, Niran Abbas Ali |
| collection | UPM |
| description | In this thesis, we consider the g-angulation existence problem of a convex geometric graph G. A triangulation on n points in convex position is a plane graph on the convex hull in which each face is a triangle except the exterior face. A g-angulation on n points in convex position is a plane graph in which each face is a g-cycle except the exterior face. In particular, the g-angulation is a triangulation if g = 3. We say that Tn is a triangulation of a graph G(V,E) if E(Tn) ⊆ E. On a given graph G, deciding whether G has a triangulation or not is known as the Triangulation Existence Problem.
Since Triangulation Existence Problem is known to be an NP-complete prob-lem, we consider the problem on a convex geometric graph G. In order to de-cide whether G admits a triangulation, we determine necessary and sufficient conditions on a subgraph F of complete convex graph Kn with |E(F)| ≤ n−1 for which G = Kn −F admits a triangulation. For |E(F)| ≥ n, we investigate the possibility of placing F in Kn for certain families of graphs F such that G admits a triangulation. These results are then applied to determine the convex skewness of G. The skewness of a graph G, denoted sk(G), is the minimum number of edges to be deleted from G such that the resulting graph is planar. Finally, we extend the triangulation existence problem to the g-angulation existence problem for a convex geometric graph G. For any g ≥ 3 we present a complete characterization of a subgraph F of Kn with |E(F)| ≤ n − 1 for which G = Kn − F admits a g-angulation. For |E(F)| ≥ n, we investigate the possibility of placing 2-regular graphs F in Kn such that G admits a g-angulation and the possibility of placing 3-regular graphs F in Kn such that G admits a 4-angulation. |
| first_indexed | 2024-03-06T10:19:08Z |
| format | Thesis |
| id | upm.eprints-76823 |
| institution | Universiti Putra Malaysia |
| language | English |
| last_indexed | 2024-03-06T10:19:08Z |
| publishDate | 2018 |
| record_format | dspace |
| spelling | upm.eprints-768232020-11-11T00:25:31Z http://psasir.upm.edu.my/id/eprint/76823/ G-angulability of convex geometric graphs al-Hakeem, Niran Abbas Ali In this thesis, we consider the g-angulation existence problem of a convex geometric graph G. A triangulation on n points in convex position is a plane graph on the convex hull in which each face is a triangle except the exterior face. A g-angulation on n points in convex position is a plane graph in which each face is a g-cycle except the exterior face. In particular, the g-angulation is a triangulation if g = 3. We say that Tn is a triangulation of a graph G(V,E) if E(Tn) ⊆ E. On a given graph G, deciding whether G has a triangulation or not is known as the Triangulation Existence Problem. Since Triangulation Existence Problem is known to be an NP-complete prob-lem, we consider the problem on a convex geometric graph G. In order to de-cide whether G admits a triangulation, we determine necessary and sufficient conditions on a subgraph F of complete convex graph Kn with |E(F)| ≤ n−1 for which G = Kn −F admits a triangulation. For |E(F)| ≥ n, we investigate the possibility of placing F in Kn for certain families of graphs F such that G admits a triangulation. These results are then applied to determine the convex skewness of G. The skewness of a graph G, denoted sk(G), is the minimum number of edges to be deleted from G such that the resulting graph is planar. Finally, we extend the triangulation existence problem to the g-angulation existence problem for a convex geometric graph G. For any g ≥ 3 we present a complete characterization of a subgraph F of Kn with |E(F)| ≤ n − 1 for which G = Kn − F admits a g-angulation. For |E(F)| ≥ n, we investigate the possibility of placing 2-regular graphs F in Kn such that G admits a g-angulation and the possibility of placing 3-regular graphs F in Kn such that G admits a 4-angulation. 2018-09 Thesis NonPeerReviewed text en http://psasir.upm.edu.my/id/eprint/76823/1/FS%202018%2077%20-%20IR.pdf al-Hakeem, Niran Abbas Ali (2018) G-angulability of convex geometric graphs. Doctoral thesis, Universiti Putra Malaysia. Graph theory Convex functions |
| spellingShingle | Graph theory Convex functions al-Hakeem, Niran Abbas Ali G-angulability of convex geometric graphs |
| title | G-angulability of convex geometric graphs |
| title_full | G-angulability of convex geometric graphs |
| title_fullStr | G-angulability of convex geometric graphs |
| title_full_unstemmed | G-angulability of convex geometric graphs |
| title_short | G-angulability of convex geometric graphs |
| title_sort | g angulability of convex geometric graphs |
| topic | Graph theory Convex functions |
| url | http://psasir.upm.edu.my/id/eprint/76823/1/FS%202018%2077%20-%20IR.pdf |
| work_keys_str_mv | AT alhakeemniranabbasali gangulabilityofconvexgeometricgraphs |