A spanning maximal planar subgraph (SMPS) T of a simple, finite, undirected graph G is a spanning subgraph of G that is also a maximal planar graph. In this paper, we introduce some methods of constructing complete 4-partite graphs Kw,x,y,z with SMPS. We utilize these methods to the SMPS problem for complete tripartite graphs to generate complete 4-partite graphs with SMPS and provide some relationships between the cardinalities of the two graphs.
Keywords: spanning maximal planar subgraph, complete 4-partite graphAlmonte, V., Gervacio, S., & Natalio, E. (2017). Complete tripartite graphs with spanning maximal planar subgraphs. World Academy of Science, Engineering Technology International Journal of Computer and Information Engineering, 11(2), p. 195. Chartrand, G.,& Zhang, P. (2009). Chromatic graph theory (pp. 109–118). Boca Raton, FL: Taylor and Francis Group.
Euler, L. (1758). Elements of the doctrine of solids. Novi Commentarii Academiae Scientiarum
Petropolitanae, 4, 71–93. Gervacio, S.V. (2008). Graphtex 2.0: 2-D and 3-D drawings and graphs in TEX and LATEX (pp. 71-73).Philippines: C & E Publishing, Inc. Liu, P.C.,& Geldmacher, R.C. (1977). On the deletion of nonplanar edges of a graph. Proceedings of the 10th SE Conf. on Comb., Graph Theory, and
Comp., 727–738. Sommerville, D.M.Y. (1929). An Introduction to The Geometry of N Dimensions (pp. 141-143). London: Methuen & Co. Ltd.