\[lem:misOnIM\].[]{data-label="fig:ourOuterstring"}](IM){width="80.00000%"}

compute a maximum independent set $S$ of $G$ in $O(1)$ time; compute $x_{med}$ and the partition $\{I_L, I_R, I_M\}$; $S(I_L)\gets$ ApproximateMISonVPG($I_L$); $S(I_R)\gets$ ApproximateMISonVPG($I_R$); $S(I_M)\gets$<span style="font-variant:small-caps;">MIS</span>$(I_M)$; $S\gets$ the larger of $S(I_L)\cup S(I_R)$ and $S(I_M)$; $S$;

\[lem:approxMISonVPGfactor\] Algorithm \[alg:approxMISonVPG\] is an $O(n^3)$-time $O(\log n)$-approximation algorithm for the [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}problem on $G$.

Clearly, the paths in $I_L$ are disjoint from those in $I_R$; so, $S(I_L)\cup S(I_R)$ is an independent set. Therefore, the solution returned by the algorithm is a feasible solution for [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}on $G$. Let $T(n)$ denote the running time of the algorithm on any [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph $G$ with $n$ vertices. If $n\leq 2$, then clearly $T(n)=O(1)$. Otherwise, we first compute $x_{med}$ in $O(n\log n)$ time by sorting all the paths $P$ by $x({\texttt{corner}}(P))$. Then, by the choice of $x_{med}$, we solve two instances of the problem recursively each of which having size $O(n/2)$. Since the algorithm of Keil et al. [@KeilMPV15] takes $O(n^3)$ time, we have $T(n)=2T(n/2)+O(n^3)$, which is solved to $T(n)=O(n^3)$.

Now, let $O^*$ be a maximum independent set in $G$. Moreover, let $O^*_L$, $O^*_R$ and $O^*_M$ denote a maximum independent set for the paths in $I_L$, $I_R$ and $I_{M}$, respectively. We 