Good spanning tree

An illustration for ${\displaystyle X_{v},Y_{v}}$ and ${\displaystyle Z_{v}}$ sets of edges

Let ${\displaystyle G_{\phi }}$ be a plane graph. Let ${\displaystyle T}$ be a rooted spanning tree of ${\displaystyle G_{\phi }}$. Let ${\displaystyle P(r,v)=(r=u_{1}),u_{2},\ldots ,(v=u_{k})}$ be the path in ${\displaystyle T}$ from the root ${\displaystyle r}$ to a vertex ${\displaystyle v\neq r}$. The path ${\displaystyle P(r,v)}$ divides the children of ${\displaystyle u_{i}}$, ${\displaystyle (1\leq i<k)}$, except ${\displaystyle u_{i+1}}$, into two groups; the left group ${\displaystyle L}$ and the right group ${\displaystyle R}$. A child ${\displaystyle x}$ of ${\displaystyle u_{i}}$ is in group ${\displaystyle L}$ and denoted by ${\displaystyle u_{i}^{L}}$ if the edge ${\displaystyle (u_{i},x)}$ appears before the edge ${\displaystyle (u_{i},u_{i+1})}$ in clockwise ordering of the edges incident to ${\displaystyle u_{i}}$ when the ordering is started from the edge ${\displaystyle (u_{i},u_{i+1})}$. Similarly, a child ${\displaystyle x}$ of ${\displaystyle u_{i}}$ is in the group ${\displaystyle R}$ and denoted by ${\displaystyle u_{i}^{R}}$ if the edge ${\displaystyle (u_{i},x)}$ appears after the edge ${\displaystyle (u_{i},u_{i+1})}$ in clockwise order of the edges incident to ${\displaystyle u_{i}}$ when the ordering is started from the edge ${\displaystyle (u_{i},u_{i+1})}$. The tree ${\displaystyle T}$ is called a good spanning tree[1] of ${\displaystyle G_{\phi }}$ if every vertex ${\displaystyle v}$ ${\displaystyle (v\neq r)}$ of ${\displaystyle G_{\phi }}$ satisfies the following two conditions with respect to ${\displaystyle P(r,v)}$.

• [Cond1] ${\displaystyle G_{\phi }}$ does not have a non-tree edge ${\displaystyle (v,u_{i})}$, ${\displaystyle i<k}$; and
• [Cond2] the edges of ${\displaystyle G_{\phi }}$ incident to the vertex ${\displaystyle v}$ excluding ${\displaystyle (u_{k-1},v)}$ can be partitioned into three disjoint (possibly empty) sets ${\displaystyle X_{v},Y_{v}}$ and ${\displaystyle Z_{v}}$ satisfying the following conditions (a)-(c)
  • (a) Each of ${\displaystyle X_{v}}$ and ${\displaystyle Z_{v}}$ is a set of consecutive non-tree edges and ${\displaystyle Y_{v}}$ is a set of consecutive tree edges.
  • (b) Edges of set ${\displaystyle X_{v}}$, ${\displaystyle Y_{v}}$ and ${\displaystyle Z_{v}}$ appear clockwise in this order from the edge ${\displaystyle (u_{k-1},v)}$.
  • (c) For each edge ${\displaystyle (v,v')\in X_{v}}$, ${\displaystyle v'}$ is contained in ${\displaystyle T_{u_{i}^{L}}}$, ${\displaystyle i<k}$, and for each edge ${\displaystyle (v,v')\in Z_{v}}$, ${\displaystyle v'}$ is contained in ${\displaystyle T_{u_{i}^{R}}}$, ${\displaystyle i<k}$.
    

    A plane graph ${\displaystyle G_{\phi }}$ (top), a good spanning tree ${\displaystyle T}$ of ${\displaystyle G_{\phi }}$ (down) solid edges are part of good spanning tree and dotted edges are non-tree edges in ${\displaystyle G_{\phi }}$ with respect to ${\displaystyle T}$.

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

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

• Spanning tree
• Schnyder realizer