Given a connected graph $G$ with a connected subgraph $H$, we can consider the uniform distribution on the set of all sequences $H_0, H_1, \dots, H_r$ where $r = |E(G) \setminus E(H)|$, $H_0 = H$, $H_r = G$, each $H_i$ ($0 \leq i \leq r$) is connected, and for each $0 \leq i < r$, $H_{i+1}$ is obtained from $H_i$ by adding an edge (and perhaps one new vertex if the added edge has one endpoint not in $H_i$). Is anything known about this sort of growth process?
Note that this is not the same process as the one in which $H_{i+1}$ is obtained from $H_i$ from choosing uniformly at random from among all the edges of $G$ not present in $H_i$ that have at least one endpoint in $H_i$. In the process I'm asking about, some of those edges will be more probable than others -- specifically, the ones that lead to there being more choices further down the road. Hence my (loose) use of the term "lookahead".
This question was inspired by discussions arising from Counting "connected" edge orderings (shellings) of the complete graph . Certainly the case in which $G$ is a complete graph and $H$ consists of a single edge is likely to be tractable.
I am especially interested in the case where $G$ is a large but finite patch of the infinite square grid and $H$ consists of a single edge somewhere in the middle of $G$. I expect that the law of the growth process would be fairly insensitive to the presence of the boundary as long as the boundary is sufficiently far away. For instance, if we take $H$ to consist of a single horizontal edge $e$, then $H_1$ can be obtained from $H_0$ by adding any of six edges, two horizontal and four vertical. I would predict that there exists probabilities $p$ and $q$ satisfying $2p+4q=1$ such that, for all $\epsilon > 0$ there exist $N$ such that as long as $G$ contains an $N$-by-$N$ square centered on $H$, then for each of those six edges, the probability that $H_1$ consists of $e$ together with the specified edge is $p \pm \epsilon$ for the horizontal edges and $q \pm \epsilon$ for the vertical edges.
If this insensitivity-to-the-presence-of-a-boundary property holds, then there'd be a well-defined way to grow the square grid one edge at a time, maintaining connectivity at each step.
It would also be natural to consider a variant in which one grows a collection of vertices rather than a collection of edges, insisting on connectedness of the induced graph at each stage. In fact, if one does this without "lookahead", it's just the Eden model. But in this case too, one could try to incorporate lookahead so that choices that allow one more freedom (i.e., more choices) further down the road would get higher probability.
It would be interesting if this sort of lookahead resulted in a variant of the Eden model with an isotropic limit shape. (The ordinary Eden model is believed to exhibit anisotropy, though I don't know if this is known rigorously.)
