Talk:Good spanning tree

Orderly Spanning Trees

As far as I can see, the definition of Good spanning trees is equivalent to the definition of Orderly Spanning Trees, which were introduced by Yi-Ting Chiang, Ching-Chi Lin and Hsueh-I Lu at SODA 2001: https://epubs.siam.org/doi/10.1137/S0097539702411381 / https://arxiv.org/abs/cs/0102006

This is their definition:

---

Let $T$ be a rooted spanning tree of a connected plane graph $H$. Two distinct nodes of $H$ are unrelated with respect to $T$ if neither of them is an ancestor of the other in $T$. An edge $e$ of $H$ is unrelated with respect to $T$ if the endpoints of $e$ are unrelated with respect to $T$. Let $v_{1},v_{2},\dots ,v_{n}$ be the counterclockwise preordering of the nodes in $T$. A node $v_{i}$ is orderly in $H$ with respect to $T$ if the neighbors of $v_{i}$ in $H$ form the following four blocks of $H$ with respect to $T$ in counterclockwise order around $v_{i}$:

• $B_{1}(v_{i})$: the parent of $v_{i}$ in $T$;
• $B_{2}(v_{i})$: the nodes $v_{j}$ with $j<i$ that are unrelated to $v_{i}$ with respect to $T$;
• $B_{3}(v_{i})$: the children of $v_{i}$ in $T$; and
• $B_{4}(v_{i})$: the nodes $v_{j}$ with $j>i$ that are unrelated to $v_{i}$ with respect to $T$, where each block could be empty.

$T$ is an orderly spanning tree of $H$ if (i) $v_{1}$ is on the contour of $H$, and (ii) each node $v_{i}$ is orderly in $H$ with respect to $T$.

---

In terms of the definition of a good spanning tree, it seems to me that

• $B_{1}(v)$ is just the parent of $v$,
• $B_{2}(v)$ is equivalent to $Z_{v}$,
• $B_{3}(v)$ is equivalent to $Y_{v}$, and
• $B_{4}(v)$ is equivalent to $X_{v}$.

So I think that the definitions are equivalent. Can someone please check whether I'm correct? PhKindermann (talk) 13:19, 25 November 2024 (UTC)