1985/02/01 by Norishige Chiba, Takao Nishizeki · 14 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Optimization and Search Problems #Combinatorics #Arboricity #Mathematics #Degeneracy (biology) #Graph #Time complexity #Clique #Upper and lower bounds #Bound graph #Planar graph #Simple graph #Discrete mathematics #Algorithm #Graph power #Line graph
paper · doi:10.1137/0214017
openalex publication_date 1985/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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 Kl 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) \leqq \lceil (2m + n)1/2 \rceil , where n is the number of vertices in G.