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...
Saved in:
| 主要作者: | |
|---|---|
| 格式: | Thesis |
| 語言: | 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 |