CMR  1.3.0
Graphic / Cographic / Planar Matroids

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: