Jump to content

Good spanning tree

From Wikipedia, the free encyclopedia
Conditions of good spanning tree

In the mathematical field of graph theory, a good spanning tree [1] of an embedded planar graph is a rooted spanning tree of whose non-tree edges satisfy the following conditions.

  • there is no non-tree edge where and lie on a path from the root of to a leaf,
  • the edges incident to a vertex can be divided by three sets and , where,
    • is a set of non-tree edges, they terminate in red zone
    • is a set of tree edges, they are children of
    • is a set of non-tree edges, they terminate in green zone

Formal definition

[edit]

Source:[1][2]

An illustration for and sets of edges

Let be a plane graph. Let be a rooted spanning tree of . Let be the path in from the root to a vertex . The path divides the children of , , except , into two groups; the left group and the right group . A child of is in group and denoted by if the edge appears before the edge in clockwise ordering of the edges incident to when the ordering is started from the edge . Similarly, a child of is in the group and denoted by if the edge appears after the edge in clockwise order of the edges incident to when the ordering is started from the edge . The tree is called a good spanning tree[1] of if every vertex of satisfies the following two conditions with respect to .

  • [Cond1] does not have a non-tree edge , ; and
  • [Cond2] the edges of incident to the vertex excluding can be partitioned into three disjoint (possibly empty) sets and satisfying the following conditions (a)-(c)
    • (a) Each of and is a set of consecutive non-tree edges and is a set of consecutive tree edges.
    • (b) Edges of set , and appear clockwise in this order from the edge .
    • (c) For each edge , is contained in , , and for each edge , is contained in , .
      A plane graph (top), a good spanning tree of (down) solid edges are part of good spanning tree and dotted edges are non-tree edges in with respect to .

Applications

[edit]

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

Finding good spanning tree

[edit]

Every planar graph has an embedding such that contains a good spanning tree. A good spanning tree and a suitable embedding can be found from in linear-time.[1] Not all embeddings of contain a good spanning tree.

See also

[edit]

References

[edit]
  1. ^ a b c d e 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. ^ a b 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.