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

وصف كامل

محفوظ في:
التفاصيل البيبلوغرافية
المؤلف الرئيسي: al-Hakeem, Niran Abbas Ali
التنسيق: أطروحة
اللغة:English
منشور في: 2018
الموضوعات:
الوصول للمادة أونلاين:http://psasir.upm.edu.my/id/eprint/76823/1/FS%202018%2077%20-%20IR.pdf
الوسوم: إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
id my-upm-ir.76823
record_format uketd_dc
spelling my-upm-ir.768232020-11-11T00:25:31Z G-angulability of convex geometric graphs 2018-09 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. Graph theory Convex functions 2018-09 Thesis http://psasir.upm.edu.my/id/eprint/76823/ http://psasir.upm.edu.my/id/eprint/76823/1/FS%202018%2077%20-%20IR.pdf text en public doctoral Universiti Putra Malaysia Graph theory Convex functions Kilicman, Adem
institution Universiti Putra Malaysia
collection PSAS Institutional Repository
language English
advisor Kilicman, Adem
topic Graph theory
Convex functions

spellingShingle Graph theory
Convex functions

al-Hakeem, Niran Abbas Ali
G-angulability of convex geometric graphs
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.
format Thesis
qualification_level Doctorate
author al-Hakeem, Niran Abbas Ali
author_facet al-Hakeem, Niran Abbas Ali
author_sort al-Hakeem, Niran Abbas Ali
title G-angulability of convex geometric graphs
title_short 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_sort g-angulability of convex geometric graphs
granting_institution Universiti Putra Malaysia
publishDate 2018
url http://psasir.upm.edu.my/id/eprint/76823/1/FS%202018%2077%20-%20IR.pdf
_version_ 1747813183850020864