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
Conditions of good spanning tree

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.