Menu
In this paper, we introduce the concept of node expansion. Node expansion is a generalization of edge subdivision and an inverse of subgraph contraction. A graph \(G_1 = (V_1, E_1)\) is an \(H\)-node expansion of \(G = (V, E)\) if and only if \(G_1\) contains a subgraph \(H = (V_H, E_H)\) such that \(V = V_1 – V_H \cup \{v\}\) and \(E = E_1 – E_H \cup \{vw | wh \in E_1 \;\text{and}\; h \in V_H\} \cup \{v\}\). The concept of node expansion is of considerable importance in modernization of networks.
We consider the node expansion problem of transforming a graph to a bipartite graph with a minimum number of node expansions using \(K_2\). We show that the \(K_2\)-node expansion problem is NP-Complete for general graphs and remains so if the input graph has maximum degree 3. However, we present a \(O({n}^2 \log n + mn + p^3)\) algorithm for the case when the input graph is restricted to be planar \(3\)-connected and output graph is required to be planar bipartite.