Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Good spanning tree

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

  • there is no non-tree edge ( u , v ) {\displaystyle (u,v)} where u {\displaystyle u} and v {\displaystyle v} lie on a path from the root of T {\displaystyle T} to a leaf,
  • the edges incident to a vertex v {\displaystyle v} can be divided by three sets X v , Y v {\displaystyle X_{v},Y_{v}} and Z v {\displaystyle Z_{v}} , where,
    • X v {\displaystyle X_{v}} is a set of non-tree edges, they terminate in red zone
    • Y v {\displaystyle Y_{v}} is a set of tree edges, they are children of v {\displaystyle v}
    • Z v {\displaystyle Z_{v}} is a set of non-tree edges, they terminate in green zone
Related Image Collections Add Image
We don't have any YouTube videos related to Good spanning tree yet.
We don't have any PDF documents related to Good spanning tree yet.
We don't have any Books related to Good spanning tree yet.
We don't have any archived web articles related to Good spanning tree yet.

Formal definition

Source:23

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

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

Applications

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

Finding good spanning tree

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

See also

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. https://doi.org/10.1016%2Fj.tcs.2015.09.004

  2. 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. https://doi.org/10.1016%2Fj.tcs.2015.09.004

  3. 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. 978-3-319-08015-4

  4. 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. https://doi.org/10.1016%2Fj.tcs.2015.09.004

  5. 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. 978-3-319-08015-4

  6. 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. https://doi.org/10.1016%2Fj.tcs.2015.09.004

  7. 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. https://doi.org/10.1016%2Fj.tcs.2015.09.004