  A graph is called a sum graph if its vertices can be labelled by distinct
positive integers such that there is an edge between two vertices if and only
if the sum of their labels is the label of another vertex of the graph. Most
papers on sum graphs consider combinatorial questions like the minimum number
of isolated vertices that need to be added to a given graph to make it a sum
graph. In this paper, we initiate the study of sum graphs from the viewpoint of
computational complexity. Notice that every $n$-vertex sum graph can be
represented by a sorted list of $n$ positive integers where edge queries can be
answered in $O(\log n)$ time. Therefore, limiting the size of the vertex labels
also upper-bounds the space complexity of storing the graph in the database.
  We show that every $n$-vertex, $m$-edge, $d$-degenerate graph can be made a
sum graph by adding at most $m$ isolated vertices to it, such that the size of
each vertex label is at most $O(n^2d)$. This enables us to store the graph
using $O(m\log n)$ bits of memory. For sparse graphs (graphs with $O(n)$
edges), this matches the trivial lower bound of $\Omega(n\log n)$. Since planar
graphs and forests have constant degeneracy, our result implies an upper bound
of $O(n^2)$ on their label size. The previously best known upper bound on the
label size of general graphs with the minimum number of isolated vertices was
$O(4^n)$, due to Kratochv\'il, Miller & Nguyen. Furthermore, their proof was
existential, whereas our labelling can be constructed in polynomial time.
