positions for each dimension. Namely, $\textit{pos}_1$, $\textit{pos}_2$, and $\textit{pos}_3$. $u.\textit{pos}_1$ is a number that indicates the relative position of $u$ with respect to other vertices in the same collinear group. Similarly $u.\textit{pos}_2$ is the position of $u$ with respect to the other vertices in the same coplanar group. Finally, $u.\textit{pos}_3$ is the actual position of $u$ in $\mathbb{R}^3$.

Localizing the nodes of a collinear group
-----------------------------------------

In this section, we describe a linear-time algorithm to localize the nodes in a given collinear group ambient in 2D. The induced graph of a collinear group is called a *unit interval graph* since all the vertices are considered to be in 1D. The algorithm takes an induced subgraph of the network graph as the input, and outputs the embedding of that subgraph onto a straight line. For the sake of simplicity, we embed the vertices onto $x$-axis. While describing the algorithm, we denote the subgraph as $G' = (V', E')$. We also assume that $G'$ is a connected graph.

If there are no cycles in a collinear group, then we can assign position to each vertex in linear time. The algorithm to achieve this is pretty straightforward.

$v_1.\textit{pos}_1 \gets 0$ $u \gets v_i$ 