style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on two subclasses of [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs.

#### Organization.

This paper is organized based on the problems as follows. We first give some notations and definitions in Section \[sec:prelimins\]. Then, we give our $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 in Section \[sec:independentSet\]. Next, we consider the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}and [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs in Section \[sec:dominatingSet\]. We first give the $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 present our results for this problem on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs in Section \[subsec:MDSonBEPG\]. We conclude the paper with a discussion on open problems in Section \[sec:conclusion\].

Notation and Definitions {#sec:prelimins}
========================

For a [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}(resp., [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}) graph $G$, we use $\langle$[$\mathcal{P}_{{\texttt{vtx}}}$ ]{}$,\mathcal{G}\rangle$ (resp., $\langle$[$\mathcal{P}_{{\texttt{edg}}}$ ]{}$,\mathcal{G}\rangle$) to denote a particular [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}(resp., [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}) representation of $G$, where [$\mathcal{P}_{{\texttt{vtx}}}$ ]{}(resp., [$\mathcal{P}_{{\texttt{edg}}}$ ]{}) is the collection of paths correspond to the vertices of $G$ and $\mathcal{G}$ is the underlying grid. Since the recognition problem is <span style="font-variant:small-caps;">NP</span>-hard on such graphs, we assume throughout this paper, that we are always given a string representation of a 