Graph / Quadrangle (Bibtex)

P183: Enumeration of all quadrangles in a graph

Input:

A connected graph $G = (V, E)$.

Output:

All quadrangles in $G$.

Complexity:

$O(\alpha(G)|E|)$ total time and $O(|E|)$ space.

Comment:

$\alpha(G)$ is the minimum number of edge-disjoint spanning forests into which $G$ can be decomposed.

Reference:

[Chiba1985] (Bibtex)