Good spanning tree

Conditions of good spanning tree

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

Formal definition

Source:

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 of Gϕ if every vertex v (v≠r) of Gϕ satisfies the following two conditions with respect to P(r,v).

Applications

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

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

See also