  We study the imbalance problem on complete bipartite graphs. The imbalance
problem is a graph layout problem and is known to be NP-complete. Graph layout
problems find their applications in the optimization of networks for parallel
computer architectures, VLSI circuit design, information retrieval, numerical
analysis, computational biology, graph theory, scheduling and archaeology. In
this paper, we give characterizations for the optimal solutions of the
imbalance problem on complete bipartite graphs. Using the characterizations, we
can solve the imbalance problem in $\mathcal{O}(\log(|V|) \cdot
\log(\log(|V|)))$ time, when given the cardinalities of the parts of the graph,
and verify whether a given solution is optimal in $O(|V|)$ time on complete
bipartite graphs. We also introduce a restricted form of proper interval
bipartite graphs on which the imbalance problem is solvable in $\mathcal{O}(c
\cdot \log(|V|) \cdot \log(\log(|V|)))$ time, where $c = \mathcal{O}(|V|)$, by
using the aforementioned characterizations.
