Good spanning tree

Conditions of good spanning tree

 an illustration for 'X_v', $Y_v$ and $Z_v$ sets of edges

In the mathematical field of graph theory, a good spanning tree T of an plane graph G is a rooted spanning tree of G whose non-tree edges satisfy the following condition.

• there is no non-tree edge (u,v) where u and v lie on a path from root to a leaf.
• the edges incident to a vertex v can be divided by three set of X_v, Y_v, Z_v
  • Set X_v is non-tree edges, each of them termites in red zone
  • Set Y_v is tree edges, each of them is a child of v
  • Set Z_v is non-tree edges, each of them termites in green zone

Formal Definition

Let $P(r,v)=(r=u_1), u_2, \ldots, (v=u_k)$ be the path in $T$ from the root $r$ to a vertex $v\ne r$. The path $P(r,v)$ divides the children of $u_i$, $(1\le i < k)$, except $u_{i+1}$, into two groups; the left group $L$ and the right group $R$. A child $x$ of $u_i$ is in group $L$ and denoted by $u_{i}^L$ if the edge $(u_i,x)$ appears before the edge $(u_i, u_{i+1})$ in clockwise ordering of the edges incident to $u_i$ when the ordering is started from the edge $(u_i,u_{i+1})$. Similarly, a child $x$ of $u_i$ is in the group $R$ and denoted by $u_{i}^R$ if the edge $(u_i,x)$ appears after the edge $(u_i, u_{i+1})$ in clockwise order of the edges incident to $u_i$ when the ordering is started from the edge $(u_i,u_{i+1})$.

% Let $E'$  be the set of all non-tree edges in $G_\phi$ with respect to $T$. % We place $T$ on $G_\phi$ and mark non-tree edges $G\setminus T$.
We call $T$  a {\it good spanning} tree of $G_\phi$ if every vertex $v$ $(v\ne r)$ of $G$ satisfies the following two conditions with respect to $P(r,v)$.

• [(Cond1)] $G$ does not have a non-tree edge $(v,u_i)$, $i<k$; and

A plane graph G (left), a good spanning tree of G (right) solid edges are part of spanning tree and dotted edges are non-tree edges

• [(Cond2)] the edges of $G$ incident to the vertex $v$ excluding $(u_{k-1},v)$ can be partitioned into three disjoint (possibly empty) sets $X_v$, $Y_v$ and $Z_v$ satisfying the following conditions (a)-(c) (see Fig.~\ref{fig:gridspliting}(b)): \begin{enumerate}
  • (a) Each of $X_v$ and $Z_v$ is a set of consecutive non-tree edges and $Y_v$ is a set of consecutive tree edges.
  • (b) Edges of set $X_v$, $Y_v$ and $Z_v$ appear clockwise in this order from the edge $(u_{k-1}, v)$.
  • (c) For each edge $(v,v')\in X_v$, $v'$ is contained in $T_{u_i^L}$, $i<k$, and for each edge $(v,v')\in Z_v$, $v'$ is contained in $T_{u_i^R}$, $i<k$.

Applications

in monotone drawing

See also

• Spanning tree
• Schnyder realizer