An efficient PQ-graph algorithm for solving the graph-realization problem

摘要

A (0, 1)-matrix is called graphic if it is a fundamental circuit matrix of a graph. Given a (0, 1)-matrix N, the graph-realization problem is (i) to determine whether N is graphic and (ii) if graphic, to realize a graph which has N as its fundamental circuit matrix. We propose a data structure called a PQ-graph based on PQ-trees and then present an efficient algorithm for solving the graph-realization problem by means of PQ-graphs. A running time required for the algorithm is O(νvα(ν, k)), where v is the number of nonzero elements of a given (0, 1)-matrix N, k is the number of rows of N and α(·, ·) is a function defined in terms of Akermann's function. Since the value of α(ν, k) is not more than 3 for all practical values of ν and k, we can solve the graph-realization problem in a running time almost proportional to ν, the number of nonzero elements of N.