Triangulability of convex graphs and convex skewness - Ali, Niran Abbas; Chia, Gek L.; Trao, Hazim Michman; Kilicman, Adem (World Scientific, 2021)
Suppose F is a subgraph of a convex complete graph Kn and F contains no boundary edge of Kn and |E(F)|≤n−1. We determine necessary and sufficient conditions on F such that Kn−F admits a triangulation. For |E(F)|≥n, we investigate the possibility of placing F in Kn such that Kn−F admits a triangulation for certain families of graphs F. These results are then applied to determine the convex skewness of the convex graphs of the form Kn−F.