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

Text FS 2018 77 - IR.pdf Download (2MB)

Actions (login required)

View Item