\(\)
Given a \(\{0,1\}\)-matrix \(M\), the graph realization problem for \(M\) asks if there exists a spanning forest such that the columns of \(M\) are incidence vectors of paths in the forest.
The problem is closely related to the recognition of network matrices, which are a large subclass of totally unimodular matrices and have many applications in mixed-integer programming.
Previously, Bixby and Wagner have designed an efficient algorithm for graph realization that grows a submatrix in a column-wise fashion whilst maintaining a graphic realization.
This paper complements their work by providing an algorithm that works in a row-wise fashion and uses similar data structures.
The main challenge in designing efficient algorithms for the graph realization problem is ambiguity as there may exist many graphs realizing \(M\).
The key insight for designing an efficient row-wise algorithm is that a graphic matrix is uniquely represented by an SPQR tree, a graph decomposition that stores all graphs with the same set of cycles.
The developed row-wise algorithm uses data structures that are compatible with the column-wise algorithm and can be combined with the latter to detect maximal graphic submatrices.