A rooted tree is a tree with a distinguished root node. When a rooted tree is embedded in a plane, a cyclic ordering is induced on the subtrees of the root. Such trees are called rooted plane trees.


Given a tree $T$, is there an algorithm that can output a rooted plane tree $T\_r$ isormorphic to $T$ such that every node $v$ except the root is labelled with a number $f(v)$ so that $v$ is the $f(v)$-th child of its pararent?


What's the complexity?



Construct a rooted plane tree with nodes labelled
Easy answer: Denote the root by $(0)$. Denote its $a\geq 0$ children by $(0,1),(0,2),\ldots,(0,a)$.
Denote recursively the $b$ children of a vertex $(0,a\_1,\ldots,a\_{k-1})$ at height $k-1$ by $(0,a\_1,\ldots,a\_{k-1},1),(0,a\_1,\ldots,a\_{k-1},2),\ldots,(0,a\_1,\ldots,a\_{k-1},b)$.


Draw the vertex $(0,a\_1,\ldots,a\_{k-1},a\_k)$ at the point $(a\_k,k)$ of $\mathbb N^2$ and join it to its ancestor at $(a\_{k-1},k-1)$ by an edge.


The answer to your question is then the function $(0,\ldots,a\_k)\longmapsto a\_k$.


The tree constructed above yields a tree which is immerged in the plane but not embedded (there is an overlay of all first descendants of vertices of given height). If you want to embed
the tree, you have to replace the first coordinate $a\_k$ of $(a\_k,k)$ by the number of
vertices $(0,b\_1,\ldots,b\_k)$ which are
lexicographically smaller than $(0,\ldots,a\_k)$.


