We build the NLC width expression for the line graph of \(G\)  from the
elimination tree \(T(G,o)\) . The NLC width expression \(X_i\)  is defined for
each vertex of \(T(G,o)\) . This however depends only on \(N^-(T(G,o), o, i)\)  and
\(N^+(G,o,i)\)  which can be obtained in \(\mbox{{\sf L}}\) . Along with the fact that
tree traversal via DFS is in \(\mbox{{\sf L}}\)  [1]}, we can
obtain the NLC width expression for the line graph of \(G\)  in \(\mbox{{\sf L}}\) : We can
represent the PEO tree using an expression
involving '(' and ')'. Note that such an expression can be output by a Logspace
transducer. This gives the structure of our NLC width expression, and now
we can fill in this expression using the NLC width operations. This only
involves local computations: for example at a node \(v_i\)  of the tree, we compute
in Logspace \(N^-(T(G,o), o, i), m\)  and \(N^+(G,o,i), r\)  and get the appropriate
expressions based on the values of \(m, r\)  as given in item 3 of the NLC width
expression above. Since we build the NLC width expression over the balanced
elimination tree of constant arity and depth \(O(\log {n})\)  via Lemma REF  and
every node in the elimination tree had atmost \(k\)  children, the parse tree of the NLC width
expression is also of height \(O(\log {n})\) .
\(\square \)
