Good spanning tree

Conditions of good spanning tree

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 Xv,Yv and Zv, where,
* Xv is a set of non-tree edges, they terminate in red zone
* Yv is a set of tree edges, they are children of v
* Zv is a set of non-tree edges, they terminate in green zone

## Contents

* 1 Formal definition
* 2 Applications
* 3 Finding good spanning tree
* 4 See also
* 5 References

## Formal definition

Source:[1][2]

An illustration for Xv,Yv and Zv sets of edges

Let Gϕ be a plane graph. Let T be a rooted spanning tree of Gϕ. Let P(r,v)=(r=u1),u2,…,(v=uk) be the path in T from the root r to a vertex v≠r. The path P(r,v) divides the children of ui, (1≤i<k), except ui+1, into two groups; the left group L and the right group R. A child x of ui is in group L and denoted by uiL if the edge (ui,x) appears before the edge (ui,ui+1) in clockwise ordering of the edges incident to ui when the ordering is started from the edge (ui,ui+1). Similarly, a child x of ui is in the group R and denoted by uiR if the edge (ui,x) appears after the edge (ui,ui+1) in clockwise order of the edges incident to ui when the ordering is started from the edge (ui,ui+1). The tree T is called a good spanning tree[1] of Gϕ if every vertex v (v≠r) of Gϕ satisfies the following two conditions with respect to P(r,v).

* [Cond1] Gϕ does not have a non-tree edge (v,ui), i<k; and
* [Cond2] the edges of Gϕ incident to the vertex v excluding (uk−1,v) can be partitioned into three disjoint (possibly empty) sets Xv,Yv and Zv satisfying the following conditions (a)-(c)
* (a) Each of Xv and Zv is a set of consecutive non-tree edges and Yv is a set of consecutive tree edges.
* (b) Edges of set Xv, Yv and Zv appear clockwise in this order from the edge (uk−1,v).
* (c) For each edge (v,v′)∈Xv, v′ is contained in TuiL, i<k, and for each edge (v,v′)∈Zv, v′ is contained in TuiR, i<k.A plane graph Gϕ (top), a good spanning tree T of Gϕ (down) solid edges are part of good spanning tree and dotted edges are non-tree edges in Gϕ 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ϕ such that Gϕ 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.

## See also

* Spanning tree
* Schnyder realizer

## References

1. ↑ 1.0 1.1 1.2 1.3 1.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.
2. ↑ 2.0 2.1 Hossain, Md Iqbal; Rahman, Md Saidur (28 June 2014). "Monotone Grid Drawings of Planar Graphs" (in en). Frontiers in Algorithmics. Lecture Notes in Computer Science. 8497. Springer, Cham. pp. 105–116. doi:10.1007/978-3-319-08016-1_10. ISBN 978-3-319-08015-4.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Good spanning tree. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Good_spanning_tree&oldid=210251"