  A dynamic graph algorithm is a data structure that answers queries about a
property of the current graph while supporting graph modifications such as edge
insertions and deletions. Prior work has shown strong conditional lower bounds
for general dynamic graphs, yet graph families that arise in practice often
exhibit structural properties that the existing lower bound constructions do
not possess. We study three specific graph families that are ubiquitous, namely
constant-degree graphs, power-law graphs, and expander graphs, and give the
first conditional lower bounds for them. Our results show that even when
restricting our attention to one of these graph classes, any algorithm for
fundamental graph problems such as distance computation or approximation or
maximum matching, cannot simultaneously achieve a sub-polynomial update time
and query time. For example, we show that the same lower bounds as for general
graphs hold for maximum matching and ($s,t$)-distance in constant-degree
graphs, power-law graphs or expanders. Namely, in an $m$-edge graph, there
exists no dynamic algorithms with both $O(m^{1/2 - \epsilon})$ update time and
$ O(m^{1 -\epsilon})$ query time, for any small $\epsilon > 0$. Note that for
($s,t$)-distance the trivial dynamic algorithm achieves an almost matching
upper bound of constant update time and $O(m)$ query time. We prove similar
bounds for the other graph families and for other fundamental problems such as
densest subgraph detection and perfect matching.
