and $I'_M$. Notice that the paths in $I'_M$ are intersecting a vertical and a horizontal line. Lahiri et al. [@LahiriMS15] showed that the [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph induced by the paths in $I_M\cap I'_M$ is a co-comparability graph for which [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}can be solved optimally in polynomial time [@KohlerM16; @Golumbic04]. They analyzed this algorithm and showed that it has an $O((\log n)^2)$-approximation factor.

To improve the approximation factor to $O(\log n)$, we avoid running the divide-and-conquer algorithm on the $y({\texttt{corner}}(P))$ of paths $P\in I_M$. Instead, we directly solve [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}on paths in $I_M$ and then return the larger of $S(I_L)\cup S(I_R)$ and $S(I_M)$ as the solution. To solve [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}on $I_M$, we show that the [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph $G_{I_M}$ induced by the paths in $I_M$ is an *outerstring graph* for which we can solve [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}optimally using the recent algorithm of Keil et al. [@KeilMPV15]. See Algorithm \[alg:approxMISonVPG\] in which <span style="font-variant:small-caps;">MIS</span>$(H)$ denotes the algorithm of Keil et al. [@KeilMPV15] for computing a maximum independent set on an outerstring graph $H$.

It remains to show that $G_{I_M}$ is an outerstring graph. Outerstring graphs were first introduced by Kratochvíl [@Kratochvil91; 