Good spanning tree

Source:

File:GST conditions.svg

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

• [Cond1] $G\_\backslash phi$ does not have a non-tree edge $(v,u\_i)$,
• [Cond2] the edges of $G\_\backslash phi$ incident to the vertex $v$ excluding $(u\_\{k-1\},v)$ can be partitioned into three disjoint (possibly empty) sets $X\_v,Y\_v$ and $Z\_v$ satisfying the following conditions (a)-(c)
• (a) Each of $X\_v$ and $Z\_v$ is a set of consecutive non-tree edges and $Y\_v$ is a set of consecutive tree edges.
• (b) Edges of set $X\_v$, $Y\_v$ and $Z\_v$ appear clockwise in this order from the edge $(u\_\{k-1\},\; v)$.
• (c) For each edge $(v,v\text{'})\backslash in\; X\_v$, $v\text{'}$ is contained in $T\_\{u\_i^L\}$,

In monotone drawing of graphs,{{cite book|last2=Rahman|first2=Md Saidur|date=28 June 2014|volume=8497|language=en|publisher=Springer, Cham|pages=105–116|doi=10.1007/978-3-319-08016-1_10|last1=Hossain|first1=Md Iqbal|title=Frontiers in Algorithmics |chapter=Monotone Grid Drawings of Planar Graphs |arxiv=1310.6084|series=Lecture Notes in Computer Science|isbn=978-3-319-08015-4|s2cid=10852618 }} in 2-visibility representation of graphs.

Every planar graph $G$ has an embedding $G\_\backslash phi$ such that $G\_\backslash phi$ 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.

• Spanning tree
• Schnyder realizer

{{reflist}}

Category:Computational problems in graph theory

Category:Spanning tree

Category:Planar graphs