We present two graph compression schemes for solving problems on dense grap
hs and complement graphs. They compress a graph or its complement graph int
o two kinds of succinct representations based on adjacency intervals and ad
jacency integers, respectively. These two schemes complement each other for
different ranges of density. Using these schemes, we develop optimal or ne
ar optimal algorithms for fundamental graph problems. In contrast to previo
us graph compression schemes, ours are simple and efficient for practical a
pplications.