Misplaced Pages

Good spanning tree

Article snapshot taken from[REDACTED] with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Conditions of 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

Formal definition

Source:

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

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 tree 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)} .

  • G ϕ {\displaystyle G_{\phi }} does not have a non-tree edge ( v , u i ) {\displaystyle (v,u_{i})} , i < k {\displaystyle i<k} ; and
  • 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} .
      A plane graph G ϕ {\displaystyle G_{\phi }} (top), a good spanning tree T {\displaystyle T} of G ϕ {\displaystyle G_{\phi }} (down) solid edges are part of good spanning tree and dotted edges are non-tree edges in G ϕ {\displaystyle G_{\phi }} with respect to T {\displaystyle T} .

Applications

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

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. 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.
  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.
Categories:
Good spanning tree Add topic