Arboricity and Subgraph Listing Algorithms

In this paper we introduce a new simple strategy into edge-searching of a graph, which is useful to the various subgraph listing problems. Applying the strategy, we obtain the following four algorithms. The first one lists all the triangles in a graph G in $O(a(G)m)$ time, where m is the number of edges of G and $a(G)$ the arboricity of G. The second finds all the quadrangles in $O(a(G)m)$ time. Since $a(G)$ is at most three for a planar graph G, both run in linear time for a planar graph. The third lists all the complete subgraphs Kₗ of order l in O(la(G)l - 2 m) time. The fourth lists all the cliques in $O(a(G)m)$ time per clique. All the algorithms require linear space. We also establish an upper bound on $a(G)$ for a graph G:a(G) (2m + n)1/2, where n is the number of vertices in G.