An almost linear-time graph realization algorithm
Donald K. Wagner · 1983
Given a (0,1)-matrix M in standard form, the graph realization problem is to determine if M is a fundamental cocycle matrix of some graph, and if so determine such a graph. An algorithm for solving the graph realization problem is described. The time complexity of the algorithm is shown to be almost linear in the number of nonzeros of M.