$3\mathrm{.}2.$ In Figure $3\mathrm{.}9$ is shown a graph displayed with a circular layout. This graph is

in fact a tree. If we assign the vertex $1$ to be the root, and we assign an order to the

other vertices with respect to $($i$)$ their distance from the root and $($ii$)$ the order of

their labels among vertices of equal distance, then we have an ordered rooted tree.

Fig. $3\mathrm{.}9$ Graph corresponding to Exercise $3\mathrm{.}2.$

A preorder traversal of this tree is a walk that visits the root first, and then visits

the vertices of the first sub$-$tree in preorder, and then the second, in a recursive

fashion, yielding the preorder listing $\{1,2,4,5,3,6,7,8,9\}.$ A postorder traversal

of this tree is a walk that traverses in postorder the vertices in the first sub$-$tree of

the root and then the second, in a recursive fashion, yielding the postorder listing

$\{4,5,2,6,8,9,7,3,1\}.$

Consider the following tree drawing algorithm. First, we assign a Cartesian coor$-$

dinate $(x_v,y_v)$ to each vertex $v,$ where $x_v$ is the rank of $v$ in the preorder traversal

list, and $y_v,$ the rank in the postorder traversal list. Second, points are connected by

a straight line if their corresponding vertices are adjacent in the original underlying

graph. Implement this algorithm for the tree shown in Figure $3\mathrm{.}9.$ Is your drawing

planar? What is its orientation? What is its effective area? How might you modify

the assignment of coordinates to vertices to reduce this area?