UPM Institutional Repository

G-angulability of convex geometric graphs


Citation

al-Hakeem, Niran Abbas Ali (2018) G-angulability of convex geometric graphs. Doctoral thesis, Universiti Putra Malaysia.

Abstract

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.


Download File

[img] Text
FS 2018 77 - IR.pdf

Download (2MB)

Additional Metadata

Item Type: Thesis (Doctoral)
Subject: Graph theory
Subject: Convex functions
Call Number: FS 2018 77
Chairman Supervisor: Professor Adem Kilicman, PhD
Divisions: Faculty of Science
Depositing User: Ms. Nur Faseha Mohd Kadim
Date Deposited: 11 Nov 2020 00:25
Last Modified: 11 Nov 2020 00:25
URI: http://psasir.upm.edu.my/id/eprint/76823
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item