hello,

i believe that the table in the attached file summarize the possible options for graph data structure with complexity;

Regards;

thanks Amer

is it only those?

Without knowing what they are being used for and how - it is difficult to say if adjacency matrices and lists are really time/space consuming. There may be efficient ways, but only w.r.to one particular problem or task at hand.

For example, we use adjacency matrices in a row-wise bit-vector fashion that is very efficient (scales well for parallel processing) that suits our purposes. But for some computations, one cannot really divide the matrix into row-wise bit-vectors.

However, to answer the question on a generic note, you have edge lists, discrete Laplacian so on, which are useful for specific purposes. For example, Laplacian matrices are very useful for computing spanning graphs and edgelists are good for middleware libraries.

So, If you can state the specific task or requirement at hand - may be some one can point in the right direction.

Thank you

Gopalakrishna (GK)

http://gopalakrishna.palem.in/

An adjacency matrix is usually only interesting for dense graphs, when |V|^2 is about |E| (with |V| = number of vertices, |E| = number of edges). Adjacency lists don't use more than a constant more space than strictly needed in the general case. They store at least an identifier for every edge, so are more space-efficient when |E|