  We introduce a dense counterpart of graph degeneracy, which extends the
recently-proposed invariant symmetric difference. We say that a graph has
sd-degeneracy (for symmetric-difference degeneracy) at most $d$ if it admits an
elimination order of its vertices where a vertex $u$ can be removed whenever it
has a $d$-twin, i.e., another vertex $v$ such that at most $d$ vertices outside
$\{u,v\}$ are neighbors of exactly one of $u, v$. The family of graph classes
of bounded sd-degeneracy is a superset of that of graph classes of bounded
degeneracy or of bounded flip-width, and more generally, of bounded symmetric
difference. Unlike most graph parameters, sd-degeneracy is not hereditary: it
may be strictly smaller on a graph than on some of its induced subgraphs. In
particular, every $n$-vertex graph is an induced subgraph of some
$O(n^2)$-vertex graph of sd-degeneracy 1. In spite of this and the breadth of
classes of bounded sd-degeneracy, we devise $\tilde{O}(\sqrt n)$-bit adjacency
labeling schemes for them, which are optimal up to the hidden polylogarithmic
factor. This is attained on some even more general classes, consisting of
graphs $G$ whose vertices bijectively map to the leaves of a tree $T$, where
transversal edges and anti-edges added to $T$ define the edge set of $G$. We
call such graph representations signed tree models as they extend the so-called
tree models (or twin-decompositions) developed in the context of twin-width, by
adding transversal anti-edges. While computing the degeneracy of an input graph
can be done in linear time, we show that deciding whether its symmetric
difference is at most 8 is co-NP-complete, and whether its sd-degeneracy is at
most 1 is NP-complete.
