LOOK AT THE PICTURE :

Maximum degree of a graph is the maximum of the degrees of its vertices.

For the graph in Figure $2,$

$($a$)$ find the minimum$-$bend orthogonal representation using flow$-$network;

show the $b-$values for all the vertices $($v$-$nodes and f$-$nodes$)$ and how you

calculated them.

Figure $2$: A graph $G$ with maximum degree $4.$

$($b$)$ Write down the orthogonal representation $H(G)$ using the following

format that we learned in the class. Walk the boundary of a face keeping

the face on your right.

$H(G)=\{H(f)|finF\},$ where $H(f)$ is face representation of the face $f$ of

$G.$

A face representation $H(f)$ of $f$ is a clockwise $($counterclockwise if $f$ is

the outer face$)$ ordered sequence of edge descriptions $(e,,)$ on $f.$

Let $e$ be an edge with the face $f$ to the right. An edge description of $e$

w$.$r$.$t $f$ is a triple $(e,,),$ where $$ is a sequence of right bend, $1$

$=$ left bend$),$ and $$ is angle $in\{\frac{}{2},,\frac{3}{2}\}$ between $e$ and next edge $e^{\text{'}}.$

$($c$)$ Find out the minimum$-$area drawing of this graph using two flow net$-$

works to calculate the width and height of the drawing.