Good spanning tree explained

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 can be divided by three sets X _{v,} Y _{v} and Z _{v} , where,X _{v} is a set of non-tree edges, they terminate in red zoneY _{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

Formal definition

Source:

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\ne r . The path P(r,v) divides the children of u _{i} , ( 1 \le 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 ^{L} _{i} 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 ^{R} _{i} 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 of G _{\phi} if every vertex v (v\ne 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} incident to the vertex v excluding (u _{k-1} ,v) can be partitioned into three disjoint (possibly empty) sets X _{v,Y} _{v} and 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 ^{L} _{i}} , i<k , and for each edge (v,v')\in Z _{v} , v' is contained in T _{u ^{R} _{i}} , i<k .

Applications

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

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. Not all embeddings of G contain a good spanning tree.

See also

• Spanning tree
• Schnyder realizer

Notes and References

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