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...
محفوظ في:
المؤلف الرئيسي: | |
---|---|
التنسيق: | أطروحة |
اللغة: | 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 |