$v.\textit{pos} \gets w(uv)$ Mark $u$ as localized Add $u.\textit{pos}_1$ into $\mathbb{F}$ $\mathbb{F}$

Algorithm \[alg:intervalgraph\] runs in $\OO(n)$ time where $n$ is the number of vertices in a collinear group. We simply process all the vertices once and assign positions until there are no vertices left. This algorithm is a strong indication that the information on grouping function reduces the number of computations dramatically.

In case where the collinear group contains cycles, we can use the algorithm proposed by Brandst[ä]{}dt et al. [@linearhamiltonian] to find the Hamiltonian path in (claw,net)-free graphs. A (claw,net)-free graph does not contain both of the graphs given in Figure \[fig:claw\] as an induced subgraph.

=\[draw, fill=white, shape=circle, radius=3pt,inner sep=1.5pt\]; (0) at (0,0) [$a$]{}; (1) at (0,1) [$b$]{}; (2) at (1,-0.5) [$d$]{}; (3) at (-1,-0.5) [$c$]{}; (0)–(1); (0)–(2); (0)–(3);

\(4) at (4,0.2) [$a$]{}; (5) at (3.7,-0.3) [$b$]{}; (6) at (4.3,-0.3) [$c$]{}; (4)–(5)–(6)–(4);

\(7) at (4, 1) [$x$]{}; (8) at (3, -0.5) [$y$]{}; (9) at (5, -0.5) [$z$]{}; (4)–(7); (5)–(8); (6)–(9);

Let us first show that interval graphs are (claw,net)-free graphs.

Every unit interval graph is claw-free.

Suppose that $K(a;b,c,d)$ is an induced claw, as shown in Figure \[fig:claw\]. Since $b$ and $c$ are not neighbors, that means 