![]() |
CMR
1.3.0
|
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.
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.
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.
The functionality is defined in graphic.h. The main functions are: