  We define a range of new coarse geometric invariants based on various
graph-theoretic measures of complexity for finite graphs, including: treewidth,
pathwidth, cutwidth, search number, topological bandwidth, bandwidth, minimal
linear arrangment, sumcut, profile, vertex and edge separation. We prove that,
for bounded degree graphs, these invariants can be used to define functions
which satisfy a strong monotonicity property, namely they are monotonically
non-decreasing with respect to regular maps, and as such have potential
applications in coarse geometry and geometric group theory. On the
graph-theoretic side, we prove asymptotically optimal upper bounds on the
treewidth, pathwidth, cutwidth, search number, topological bandwidth, vertex
separation, edge separation, minimal linear arrangement, sumcut and profile for
the family of all finite subgraphs of any bounded degree graph whose separation
profile is known to be of the form $r^a\log(r)^b$ for some $a>0$. This large
class includes the Diestel-Leader graph, all Cayley graphs of non-virtually
cyclic polycyclic groups, uniform lattices in almost all connected unimodular
Lie groups, and certain hyperbolic groups.
