论文部分内容阅读
The skewness of a graph G,denoted by sk(G),is the minimum number of edges in G whose removal results in a planar graph. It is an important parameter that measures how close a graph is to planarity,and it is complementary,and computationally equivalent,to the Maximum Planar Subgraph Problem. For any connected graph G on p vertices and q edges with girth g,one can easily verify that sk(G)≥π (G),where π (G)=「q? g/g?2 (p?2)(」),and the graph G is said to be π-skew if equality holds. The concept of π-skew was first proposed by G. L. Chia and C. L. Lee. The π-skew graphs with girth 3 are precisely the graphs that contain a triangulation as a spanning subgraph. The purpose of this paper is to explore the properties of π-skew graphs. Some families of π-skew graphs are obtained by applying these properties,including join of two graphs,complete multipartite graphs and Cartesian product of two graphs. We also discuss the threshold for the existence of a spanning triangulation. Among other results some suffi cient conditions regarding the regularity and size of a graph,which ensure a spanning triangulation,are given.