The computational complexity of the minimum fill-in problem of graphs is discussed in this paper. We prove that this problem is NP-complete even for bipartite graphs and square graphs. A linear time algorithm for outerplane graphs is got. The computational complexity of the minimum fill-in problem of graphs is discussed in this paper. We prove that this problem is NP-complete even for bipartite graphs and square graphs. A linear time algorithm for outerplane graphs is got.

The computational complexity of the minimum fill-in problem of graphs is discussed in this paper. We prove that this problem is NP-complete even for bipartite graphs and square graphs. A linear time algorithm for outerplane graphs is got.