An Algorithm for the Blocks and Cutnodes of a Graph An efficient method is presented for finding blocks and cutnodes of an arbitrary undirected graph. The graph may be represented either (i) as an ordered list of edges or (ii) as a packed adjacency matrix. If w denotes the word length of the machine employed, the storage (in machine words) required for a graph with n nodes and m edges increases essentially as 2(m+n) in case (i), or (n^2)/win case (ii). A spanning tree with labeled edges is grown, two edges finally bearing different labels if and only if they belong to different blocks. For both representations the time required to analyze a graph on n nodes increases as n^G where G depends on the type of graph, 1 <= G <= 2, and both bounds are attained. Values of G are derived for each of several suitable families of test graphs, generated by an extension of the web grammar approach. The algorithm is compared in detail with that proposed by Read for which 1 <= G <= 3. CACM July, 1971 Paton, K. algorithm, block, block-cutpoint-tree, cutnode, fundamental cycle set, graph, lobe, lobe decomposition graph, separable, spanning tree, web grammar 5.32 CA710705 JB February 3, 1978 8:58 AM 1961 4 2177 2177 4 2177 2763 4 2177 1847 5 2177 2177 5 2177 2177 5 2177 2177 5 2177 2490 5 2177 2177 6 2177