Computing certificates for the graph realization problem on 3-connected graphs

For the graph realization problem we are given a binary matrix, and we need decide if there exists a graph that is represented by the given matrix. If such a graph can be found, that matrix is graphic. The already exist algorithms that determine the graphicness of matrices. In this paper we present an algorithm that can reduce a non-graphic matrix with the use of a 3-connected graph represented by some graphic submatrix of the given matrix. The output can be used as certificate to verify the non-graphicness and could give some insight as to why a given matrix is non-graphic.