On the Planar Decomposition of a Complete Bipartite Graph
Isao Shirakawa, Hiromitsu Takahashi, Hiroshi Ozaki · SIAM Journal on Applied Mathematics · 1968
This paper considers the planar decomposition of a complete bipartite graph, that is, the decomposition of a complete bipartite graph into planar subgraphs such that the union of all these planar subgraphs is the original complete bipartite graph and any two of them have no edge in common. This problem is motivated by the synthesis of a given logical network consisting only of NOR and/or NAND elements with as few integrated circuits as possible. The main result of this paper is that the smallest number of planar subgraphs into which a complete bipartite graph $K_{n,n} $ can be decomposed does not exceed $[ n/3] + 1$, where $[ x ]$ stands for the minimum integer not less than x.