Good spanning tree

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

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

In the mathematical field of graph theory, a good spanning tree ^[1] $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$ $v$ can be divided by three sets $X_{v},Y_{v}$ $X_{v},Y_{v}$ and $Z_{v}$ $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
  Conditions of good spanning tree

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\neq r$ . The path $P(r,v)$ divides the children of $u_{i}$ , $(1\leq 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})$ . The tree $T$ is called a good spanning tree^[1] of $G_{\phi }$ if every vertex $v$ $(v\neq r)$ of $G_{\phi }$ satisfies the following two conditions with respect to $P(r,v)$ .

[Cond1] $G_{\phi }$ does not have a non-tree edge $(v,u_{i})$ , $i<k$ ; and

[Cond2] the edges of $G_{\phi }$ $G_{\phi }$ incident to the vertex $v$ $v$ excluding $(u_{k-1},v)$ $(u_{k-1},v)$ can be partitioned into three disjoint (possibly empty) sets $X_{v},Y_{v}$ $X_{v},Y_{v}$ and $Z_{v}$ $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_{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$ .
  A plane graph $G_{\phi }$ (top), a good spanning tree $T$ of $G_{\phi }$ (down) solid edges are part of good spanning tree and dotted edges are non-tree edges in $G_{\phi }$ with respect to $T$ .

Applications

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

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 ^[1]. Not all embeddings of $G$ contain a good spanning tree.

References

^ ^a ^b ^c ^d 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.
^ Hossain, Md Iqbal; Rahman, Md Saidur (28 June 2014). "Monotone Grid Drawings of Planar Graphs". Frontiers in Algorithmics. Springer, Cham: 105–116. doi:10.1007/978-3-319-08016-1_10.

Category:Spanning tree Category:Computational problems in graph theory Category:Axiom of choice

[:0-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.

[:1-2] Hossain, Md Iqbal; Rahman, Md Saidur (28 June 2014). "Monotone Grid Drawings of Planar Graphs". Frontiers in Algorithmics. Springer, Cham: 105–116. doi:10.1007/978-3-319-08016-1_10.

[1]

[2]

Formal Definition

Applications

Finding Good Spanning Tree

See also

References