Furthermore, Chaplick et al. [@ChaplickCS11] considered the recognition problem for some restricted classes of B$_0$-VPG graphs.

#### Related work and our results.

The decision version of the [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}problem on [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs was shown to be <span style="font-variant:small-caps;">NP</span>-complete by Lahiri et al. [@LahiriMS15] who also gave an $O((\log n)^2)$-approximation algorithm for this problem. Notice that the best known algorithm for [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}on arbitrary string graphs has an approximation factor $n^{\epsilon}$, for some $\epsilon>0$ [@FoxP11].

-   We give a polynomial-time $O(\log n)$-approximation algorithm for the [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}problem on [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs, improving the $O((\log n)^2)$-approximation algorithm of Lahiri et al. [@LahiriMS15].

Our algorithm is actually based on that of Lahiri et al. [@LahiriMS15], which is a divide-and-conquer approach [@clrsBook; @deBergBook]. However, instead of solving a special subproblem using a secondary divide-and-conquer, we show how to solve that subproblem directly and improve the approximation factor. For [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs, Asinowski et al. [@AsinowskiCGLLS12] proved that every circle graph is a [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph. A circle graph is the intersection graph of a set of chords of a circle; that is, each vertex corresponds to a chord of 