On complete 4-partite graphs with spanning maximal planar subgraphs

A spanning maximal planar subgraph T = (V E0) is a spanning planar subgraph of a simple, finite, undirected graph G = (V E), with the property of being a maximal planar graph. That is, there exists a drawing of T on the plane, such that there are no edge-crossings and all the regions of T are bounded by exactly three edges. We refer to finding a spanning maximal planar subgraph of G, as the SMPS problem. This problem belongs to the problem of graph planarization, and we discuss how the SMPS is related to the concepts of graph planarization. In this study, we tackle the SMPS problem for complete 4-partite graphs. It is shown that for the class of graphs K1 1 1 z and K1 1 y z , a SMPS will exist if and only if z 2 f1 2g and jy {u100000} zj 1, respectively. The SMPS of these graphs were utilized to construct SMPS for more general complete 4-partite graphs K1 x y z and Kw x y z with larger order, leading to relationships between the cardinalities w x y and z. Such construction of larger SMPS requires various methods of adding vertices, and consequently edges, to a maximal planar graph. These methods are elaborated in detail, and the conditions when they can be carried out are discussed. Algorithms were developed with the aid of these methods in generating larger SMPS. It is also presented here how the SMPS problem for complete tripartite graphs could be used to solve some problems in the complete 4-partite case. The results produced in the study were applied to complete 4-partite graphs with order at most 15, to classify which among the configurations of cardinalities of the four partite sets induce a complete 4-partite graph with a SMPS. A necessary and sufficient condition in order for a SMPS to exist in any complete 4-partite graph was also found in this research.