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
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
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 ↩
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 ↩
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 ↩
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 ↩
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 ↩
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 ↩
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 ↩