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

Full description

Saved in:

Bibliographic Details
Main Author:	al-Hakeem, Niran Abbas Ali
Format:	Thesis
Language:	English
Published:	2018
Subjects:	Graph theory Convex functions
Online Access:	http://psasir.upm.edu.my/id/eprint/76823/1/FS%202018%2077%20-%20IR.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

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

G-angulability of convex geometric graphs

Similar Items