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.