A graph parameter possibly related to treewidth
Though we've chatted about this in person before, I'll add this in the hope that this will allow someone else to provide a complete answer.
In your process of adding vertices, define a partial function $f:V(G) \rightharpoonup V(G)$ from each vertex $v$ which gets used, to the vertex which was added when $v$ got used. Then it turns out that $f$ is a (causal) flow function (p. 39), which is a restricted version of a path cover. Indeed, your description of these graphs of &quot;complexity k&quot; (given a set of vertices which are to be the initially unused vertices, and the final unused vertices) is precisely the star decomposition of a &quot;geometry&quot; with a causal flow (p. 46 of the above article).
Although these &quot;causal flows&quot; have been studied mainly in the context of (measurement-based) quantum computation — where they are motivated by certain structures of unitary circuits — there are graph-theoretic results about them which are totally divorced from quantum computation:

Uniqueness modulo endpoints: the graphs with &quot; complexity $k$ &quot; are precisely those for which there exist (possibly intersecting) sets $S,T \subseteq V(G)$, both of size $k$, such that $G$ has exactly one path cover of size $k$ whose paths start in $S$ and end in $T$.
Extremal graphs: A graph on $n$ vertices which has &quot;complexity $k$&quot; has at most $kn - \binom{k+1}{2}$ edges.

Using these results, and given a candidate pair of sets $S,T$, determining whether or not they &quot;subtend&quot; a unique path cover in this way can be determined in time $O(k^2 n)$; but finding whether or not such sets of endpoints exist that is the apparent difficulty, and the extremal result above (which is only a necessary condition) seems to represent the state of the art in efficient criteria to determine whether such sets exist.