largest solution as the final answer. By Lemma \[lem:approxMISonVPGfactor\], our final answer is at least $\frac{1}{4}(\log n)$ times an optimal solution for the original problem, where $\lvert$[$\mathcal{P}_{{\texttt{vtx}}}$ ]{}$\rvert=n$. This gives us the main result of this section.

\[thm:approxMISonVPG\] There exists an $O(n^3)$-time $O(\log n)$-approximation algorithm for the [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}problem on any [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph with $n$ vertices.

Dominating Set {#sec:dominatingSet}
==============

In this section, we consider the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on *one-string* [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}and [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs. We first give our $O(1)$-approximation algorithm for this problem on one-string [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs in Section \[subsec:MDSonBVPG\], and then will present our results for this problem on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs in Section \[subsec:MDSonBEPG\].

One-string [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}Graphs {#subsec:MDSonBVPG}
-----------------------------------------------------------------------------

Recall that Asinowski et al. [@AsinowskiCGLLS12] proved that every circle graph is a one-string [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph. Since [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}is known to be [<span style="font-variant:small-caps;">APX</span>-hard ]{}on circle graphs [@DamianP06], the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem becomes [<span style="font-variant:small-caps;">APX</span>-hard ]{}also on one-string [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs. In the following, we give an $O(1)$-approximation algorithm for [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on one-string [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs. To our knowledge, this is the first $O(1)$-approximation algorithm for this problem on 