Good Spanning Tree

In the mathematical field of graph theory, a good spanning tree $T$ of an embedded planar graph $G$ is a rooted spanning tree of ''$G$'' whose non-tree edges satisfy the following conditions.
*there is no non-tree edge $(u,v)$ where $u$ and $v$ lie on a path from the root of $T$ to a leaf,
* the edges incident to a vertex $v$ can be divided by three sets $X_v, Y_v$ and $Z_v$, where,
** $X_v$ is a set of non-tree edges, they terminate in red zone
** $Y_v$ is a set of tree edges, they are children of $v$
** $Z_v$ is a set of non-tree edges, they terminate in green zone

Formal definition

Let $G_\phi$ be a plane graph. Let $T$ be a rooted spanning tree of $G_\phi$. 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_$, 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_^L$ if the edge $(u_i,x)$ appears before the edge $(u_i, u_)$ in clockwise ordering of the edges incident to $u_i$ when the ordering is started from the edge $(u_i,u_)$. Similarly, a child $x$ of $u_i$ is in the group $R$ and denoted by $u_^R$ if the edge $(u_i,x)$ appears after the edge $(u_i, u_)$ in clockwise order of the edges incident to $u_i$ when the ordering is started from the edge $(u_i,u_)$. The tree $T$ is called a ''good spanning tree'' of $G_\phi$ if every vertex $v$ $(v\ne r)$ of $G_\phi$ satisfies the following two conditions with respect to $P(r,v)$.

* ond1$G_\phi$ does not have a non-tree edge $(v,u_i)$, i; and
* ond2the edges of $G_\phi$ incident to the vertex $v$ excluding $(u_,v)$ can be partitioned into three disjoint (possibly empty) sets $X_v,Y_v$ and $Z_v$ satisfying the following conditions (a)-(c)
** (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_, v)$.
** (c) For each edge $(v,v')\in X_v$, $v'$ is contained in $T_$, i, and for each edge $(v,v')\in Z_v$, $v'$ is contained in $T_$, i.

Applications

In monotone drawing of graphs, in 2-visibility representation of graphs.

Finding good spanning tree

Every planar graph $G$ has an embedding $G_\phi$ such that $G_\phi$ contains a good spanning tree. A good spanning tree and a suitable embedding can be found from $G$ in linear-time. Not all embeddings of $G$ contain a good spanning tree.

See also

* Spanning tree
* Schnyder realizer

References

{{reflist

Computational problems in graph theory
Spanning tree
Planar graphs