Good spanning tree

Conditions of good spanning tree

In the mathematical field of graph theory, a good spanning tree [1] ${\displaystyle T}$ of an embedded planar graph ${\displaystyle G}$ is a rooted spanning tree of ${\displaystyle G}$ whose non-tree edges satisfy the following conditions.

• there is no non-tree edge ${\displaystyle (u,v)}$ where ${\displaystyle u}$ and ${\displaystyle v}$ lie on a path from the root of ${\displaystyle T}$ to a leaf,
• the edges incident to a vertex ${\displaystyle v}$ can be divided by three sets ${\displaystyle X_{v},Y_{v}}$ and ${\displaystyle Z_{v}}$, where,
  • ${\displaystyle X_{v}}$ is a set of non-tree edges, they terminate in red zone
  • ${\displaystyle Y_{v}}$ is a set of tree edges, they are children of ${\displaystyle v}$
  • ${\displaystyle Z_{v}}$ is a set of non-tree edges, they terminate in green zone

Formal definition

Source:[1][2]

An illustration for ${\displaystyle X_{v},Y_{v}}$ and ${\displaystyle Z_{v}}$ sets of edges

Let ${\displaystyle G_{\phi }}$ be a plane graph. Let ${\displaystyle T}$ be a rooted spanning tree of ${\displaystyle G_{\phi }}$. Let ${\displaystyle P(r,v)=(r=u_{1}),u_{2},\ldots ,(v=u_{k})}$ be the path in ${\displaystyle T}$ from the root ${\displaystyle r}$ to a vertex ${\displaystyle v\neq r}$. The path ${\displaystyle P(r,v)}$ divides the children of ${\displaystyle u_{i}}$, ${\displaystyle (1\leq i<k)}$, except ${\displaystyle u_{i+1}}$, into two groups; the left group ${\displaystyle L}$ and the right group ${\displaystyle R}$. A child ${\displaystyle x}$ of ${\displaystyle u_{i}}$ is in group ${\displaystyle L}$ and denoted by ${\displaystyle u_{i}^{L}}$ if the edge ${\displaystyle (u_{i},x)}$ appears before the edge ${\displaystyle (u_{i},u_{i+1})}$ in clockwise ordering of the edges incident to ${\displaystyle u_{i}}$ when the ordering is started from the edge ${\displaystyle (u_{i},u_{i+1})}$. Similarly, a child ${\displaystyle x}$ of ${\displaystyle u_{i}}$ is in the group ${\displaystyle R}$ and denoted by ${\displaystyle u_{i}^{R}}$ if the edge ${\displaystyle (u_{i},x)}$ appears after the edge ${\displaystyle (u_{i},u_{i+1})}$ in clockwise order of the edges incident to ${\displaystyle u_{i}}$ when the ordering is started from the edge ${\displaystyle (u_{i},u_{i+1})}$. The tree ${\displaystyle T}$ is called a good spanning tree[1] of ${\displaystyle G_{\phi }}$ if every vertex ${\displaystyle v}$ ${\displaystyle (v\neq r)}$ of ${\displaystyle G_{\phi }}$ satisfies the following two conditions with respect to ${\displaystyle P(r,v)}$.

• [Cond1] ${\displaystyle G_{\phi }}$ does not have a non-tree edge ${\displaystyle (v,u_{i})}$, ${\displaystyle i<k}$; and
• [Cond2] the edges of ${\displaystyle G_{\phi }}$ incident to the vertex ${\displaystyle v}$ excluding ${\displaystyle (u_{k-1},v)}$ can be partitioned into three disjoint (possibly empty) sets ${\displaystyle X_{v},Y_{v}}$ and ${\displaystyle Z_{v}}$ satisfying the following conditions (a)-(c)
  • (a) Each of ${\displaystyle X_{v}}$ and ${\displaystyle Z_{v}}$ is a set of consecutive non-tree edges and ${\displaystyle Y_{v}}$ is a set of consecutive tree edges.
  • (b) Edges of set ${\displaystyle X_{v}}$, ${\displaystyle Y_{v}}$ and ${\displaystyle Z_{v}}$ appear clockwise in this order from the edge ${\displaystyle (u_{k-1},v)}$.
  • (c) For each edge ${\displaystyle (v,v')\in X_{v}}$, ${\displaystyle v'}$ is contained in ${\displaystyle T_{u_{i}^{L}}}$, ${\displaystyle i<k}$, and for each edge ${\displaystyle (v,v')\in Z_{v}}$, ${\displaystyle v'}$ is contained in ${\displaystyle T_{u_{i}^{R}}}$, ${\displaystyle i<k}$.

    

    A plane graph ${\displaystyle G_{\phi }}$ (top), a good spanning tree ${\displaystyle T}$ of ${\displaystyle G_{\phi }}$ (down) solid edges are part of good spanning tree and dotted edges are non-tree edges in ${\displaystyle G_{\phi }}$ with respect to ${\displaystyle T}$.

Applications

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

Finding good spanning tree

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

See also

• Spanning tree
• Schnyder realizer

References

1. Hossain, Md. Iqbal; Rahman, Md. Saidur (23 November 2015). "Good spanning trees in graph drawing". Theoretical Computer Science. 607: 149–165. doi:10.1016/j.tcs.2015.09.004.
2. Hossain, Md Iqbal; Rahman, Md Saidur (28 June 2014). "Monotone Grid Drawings of Planar Graphs". Frontiers in Algorithmics. Lecture Notes in Computer Science. Vol. 8497. Springer, Cham. pp. 105–116. arXiv:1310.6084. doi:10.1007/978-3-319-08016-1_10. ISBN 978-3-319-08015-4. S2CID 10852618.