A Comparison of Methods used to Represent Graphs on a Computer

Abstract

In general graph theorists have a limited knowledge of computers and computing, and are unaware of the possible variations of representation available, and in what circumstances which representation would be better. To assist in this regard a comparative study of currently used methods for representing graphs on a computer was made. The comparison was over four regions of interest, a) time efficiency, bl representation flexibility, c) space efficiency, d) language flexibility. The comparison was made for five classe·s of graph theoretic problems, a) graph creation, b) path finding, c) structure finding, d) graph traversal, e) graph analysis. A minimal set of graph operations for graph manipulation was also provided in the cour.se of the comparison.