Good spanning tree

• 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

Source:

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 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 , .

Applications

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

Finding good spanning tree

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

See also

• Spanning tree
• Schnyder realizer

References