CMR  1.3.0
Graphic / Cographic / Planar Matrices

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.

# Recognizing Graphic Matrices

The command

cmr-graphic IN-MAT [OPTION]...


determines whether the matrix given in file IN-MAT is (co)graphic.

Options:

• -i FORMAT Format of file IN-MAT, among dense for dense-matrix and sparse for sparse-matrix; default: dense.
• -t Test for being cographic; default: test for being graphic.
• -G OUT-GRAPH Write a graph to file OUT-GRAPH; default: skip computation.
• -T OUT-TREE Write a spanning tree to file OUT-TREE; default: skip computation.
• -D OUT-DOT Write a dot file OUT-DOT with the graph and the spanning tree; default: skip computation.
• -N NON-SUB Write a minimal non-(co)graphic submatrix to file NON-SUB; default: skip computation.
• -s Print statistics about the computation to stderr.

If IN-MAT is - then the matrix is read from stdin. If OUT-GRAPH, OUT-TREE, OUT-DOT or NON-SUB is - then the graph (resp. the tree, dot file or non-(co)graphic submatrix) is written to stdout.

## 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 corresponding functions in the library are

and are defined in network.h.

# Computing graphic matrices

The command

cmr-graphic -c IN-GRAPH OUT-MAT [OPTION]...


computes a (co)graphic matrix corresponding to the graph from file IN-GRAPH and writes it to OUT-MAT.

Options:

• -o FORMAT Format of file OUT-MAT, among dense for dense-matrix and sparse for sparse-matrix; default: dense.
• -t Return the transpose of the graphic matrix.
• -T IN-TREE Read a tree from file IN-TREE; default: use first specified arcs as tree edges.
• -s Print statistics about the computation to stderr.

If IN-GRAPH or IN-TREE is - then the graph (resp. tree) is read from stdin. If OUT-MAT is - then the matrix is written to stdout.

## C Interface

The corresponding function in the library is

and is defined in network.h.