Файл:GST conditions.svgAn illustration for <math>X_v , Y_v </math> and <math>Z_v</math> sets of edges
Let <math>G_\phi</math> be a plane graph. Let <math>T</math> be a rooted spanning tree of <math>G_\phi</math>. Let <math>P(r,v)=(r=u_1), u_2, \ldots, (v=u_k)</math> be the path in <math>T</math> from the root <math>r</math> to a vertex <math>v\ne r</math>. The path <math>P(r,v)</math> divides the children of <math>u_i</math>, <math>(1\le i < k)</math>, except <math>u_{i+1}</math>, into two groups; the left group <math>L</math> and the right group <math>R</math>. A child <math>x</math> of <math>u_i</math> is in group <math>L</math> and denoted by <math>u_{i}^L</math> if the edge <math>(u_i,x)</math> appears before the edge <math>(u_i, u_{i+1})</math> in clockwise ordering of the edges incident to <math>u_i</math> when the ordering is started from the edge <math>(u_i,u_{i+1})</math>. Similarly, a child <math>x</math> of <math>u_i</math> is in the group <math>R</math> and denoted by <math>u_{i}^R</math> if the edge <math>(u_i,x)</math> appears after the edge <math>(u_i, u_{i+1})</math> in clockwise order of the edges incident to <math>u_i</math> when the ordering is started from the edge <math>(u_i,u_{i+1})</math>. The tree <math>T</math> is called a good spanning tree[1] of <math>G_\phi</math> if every vertex <math>v</math> <math>(v\ne r)</math> of <math>G_\phi</math> satisfies the following two conditions with respect to <math>P(r,v)</math>.
[Cond1] <math>G_\phi</math> does not have a non-tree edge <math>(v,u_i)</math>, <math>i<k</math>; and
[Cond2] the edges of <math>G_\phi</math> incident to the vertex <math>v</math> excluding <math>(u_{k-1},v)</math> can be partitioned into three disjoint (possibly empty) sets <math>X_v,Y_v</math> and <math>Z_v</math> satisfying the following conditions (a)-(c)
(a) Each of <math>X_v</math> and <math>Z_v</math> is a set of consecutive non-tree edges and <math>Y_v</math> is a set of consecutive tree edges.
(b) Edges of set <math>X_v</math>, <math>Y_v</math> and <math>Z_v</math> appear clockwise in this order from the edge <math>(u_{k-1}, v)</math>.
(c) For each edge <math>(v,v')\in X_v</math>, <math>v'</math> is contained in <math>T_{u_i^L}</math>, <math>i<k</math>, and for each edge <math>(v,v')\in Z_v</math>, <math>v'</math> is contained in <math>T_{u_i^R}</math>, <math>i<k</math>.Файл:Good spanning tree example.svgA plane graph <math>G_\phi</math> (top), a good spanning tree <math>T</math> of <math>G_\phi</math> (down) solid edges are part of good spanning tree and dotted edges are non-tree edges in <math>G_\phi</math> with respect to <math>T</math>.
Applications
In monotone drawing of graphs,[2] in 2-visibility representation of graphs.[1]
Finding good spanning tree
Every planar graph <math>G</math> has an embedding <math>G_\phi</math> such that <math>G_\phi</math> contains a good spanning tree. A good spanning tree and a suitable embedding can be found from <math>G</math> in linear-time.[1] Not all embeddings of <math>G</math> contain a good spanning tree.
