Algorithm 447: efficient algorithms for graph manipulation

ABSTRACT

Efficient algorithms are presented for partitioning a graph into connected components, biconnected components and simple paths. The algorithm for partitioning of a graph into simple paths of iterative and each iteration produces a new path between two vertices already on paths. (The start vertex can be specified dynamically.) If V is the number of vertices and E is the number of edges, each algorithm requires time and space proportional to max (V, E) when executed on a random access computer.

REFERENCES

• 1: Fisher, G.J. Computer recognition and extraction of planar graphs from the incidence matrix. IEEE Trans. in Orcuit Theory CT-13, (June 1966), 154-163.
• 2: Harary, F. Graph Theory. Addison-Wesley, Reading, Mass., 1969.
• 3: Holt, R., and Reingold, E. On the time required to detect cycles and connectivity in directed graphs. Comput. Sci. TR 70-33, Cornell U. Ithaca, N.Y.
• 4: John E. Hopcroft , Robert E Tarjan, Planarity testing in V log V steps: extended abstract, Stanford University, Stanford, CA, 1971
• 5: Lempel, A., Even, S., and Cederbaum, I. An algorithm for planarity testing of graphs. Theory of Graphs: International Symposium: Rome, July 1966. P. Rosenstiehl (Ed.) Gordon and Breach, New York, 1967, pp. 215-232.
• 6: Keith Paton, An algorithm for the blocks and cutnodes of a graph, Communications of the ACM, v.14 n.7, p.468-475, July 1971 [doi>10.1145/362619.362628]
• 7: Robert William Shirey, Implementation and analysis of efficient graph planarity testing algorithms, 1969

INDEX TERMS

Keywords:
analysis of algorithms, graph manipulation, graphs