Generating Spanning Maximal Planar Subgraphs of Complete 4-Partite Graphs
T.J.B. Estrada and I.B. Jos (pp. 56-63)
Abstract
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.