Recognizing Series-Parallel Matrices in Linear Time

A series-parallel matrix is a binary matrix that can be obtained from an empty matrix by successively adjoining rows or columns that are copies of an existing row/column or have at most one one-entry. Equivalently, series-parallel matrices are representation matrices of graphic matroids of series-parallel graphs, which can be recognized in linear time. We propose an algorithm that, for an m-by-n matrix A with k nonzeros, determines in expected time whether A is series-parallel or returns a minimal non-seriesparallel submatrix of A. We complement the developed algorithm by an efficient O(m + n + k)implementation and report about computational results.