Two new compact transitive closure representations are presented. The first representation is based on intervals of consecutively numbered strong components. The representation generalizes a previous method for compressing the transitive closure of an acyclic graph. The new representation also handles cyclic graphs, and it can be computed more efficiently than the previous representation. The second new representation generalizes the chain decomposition representation for acyclic graphs to handle cyclic graphs.
Simulation experiments show that the interval representation is superior to the commonly used adjacency list representation. The experiments indicate that the interval representation requires typically at most a space linear to the number of vertices in the input graph. The experiments also indicate that with the interval representation and the new algorithms, the transitive closure can be computed typically in time linear to the size of the input graph.