Let \( G = (V,E) \) be a graph and let \( T \) be a spanning forest. The matrix \( M(G,T) \in \{0,1\}^{T \times (E \setminus T)} \) defined via

\[ M(G,T)_{e,f} := \begin{cases} 1 & \text{if } e \text{ is contained in the unique cycle of } T \cup \{f\} \\ 0 & \text{otherwise} \end{cases} \]

is called the graphic matrix of \( G \) with respect to \( T \). A binary matrix \( M \) is called graphic if there exists a graph \( G \) with a spanning forest \( T \) such that \( M = M(G,T) \). Moreover, \( M \) is called cographic if \( M^{\textsf{T}} \) is graphic, and it is called planar if it is graphic and cographic.

Usage

The executable cmr-graphic converts graphs to graphic matrices and vice versa. In particular, for a given matrix \( M \), it determines whether \( M \) is (co)graphic.

./cmr-graphic [OPTION]... FILE

Options:

-i FORMAT Format of input FILE; default: dense.
-o FORMAT Format of output; default: edgelist if input is a matrix and dense if input is a graph.
-t Tests for being / converts to cographic matrix.
n Output the elements of a minimal non-(co)graphic submatrix.
N Output a minimal non-(co)graphic submatrix.
s Print statistics about the computation to stderr.

Formats for matrices are dense-matrix, sparse-matrix. Formats for graphs are edge-list and dot. If FILE is -, then the input will be read from stdin.

Algorithm

The implemented recognition algorithm is based on An Almost Linear-Time Algorithm for Graph Realization by Robert E. Bixby and Donald K. Wagner (Mathematics of Operations Research, 1988). For a matrix \( M \in \{0,1\}^{m \times n}\) with \( k \) nonzeros it runs in \( \mathcal{O}( k \cdot \alpha(k, m) ) \) time, where \( \alpha(\cdot) \) denotes the inverse Ackerman function.

C Interface

The functionality is defined in graphic.h. The main functions are:

CMRcomputeGraphicMatrix() constructs a graphic matrix for a given graph.
CMRtestGraphicMatrix() tests a matrix for being graphic.
CMRtestCographicMatrix() tests a matrix for being cographic.