such graphs. For the rest of this section, let $G$ be a one-string [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graph with $n$ vertices, and let $\langle$[$\mathcal{P}_{{\texttt{vtx}}}$ ]{}$,\mathcal{G}\rangle$ denote its string representation.

Our algorithm is based on first formulating the problem on $G$ as a hitting set problem and then computing a small $\varepsilon$-net for the corresponding instance of the hitting set problem. Having such an $\varepsilon$-net along with the technique of Brönnimann and Goodrich [@BronnimannG95] gives us an $O(1)$-approximation algorithm for [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on $G$. We first formulate [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on $G$ as a hitting set problem and then describe our $\varepsilon$-net for it.

[r]{}[0.35]{} ![image](newCross-5) \[fig:aCross\]

#### Hitting set.

A *set system* is a pair $\mathcal{R}=(\mathcal{U}, \mathcal{S})$, where $\mathcal{U}$ is a ground set of elements and $\mathcal{S}$ is a collection of subsets of $\mathcal{U}$. A *hitting set* for the set system $(\mathcal{U}, \mathcal{S})$ is a subset $M$ of $\mathcal{U}$ such that $M\cap S\neq \emptyset$ for all $S\in\mathcal{S}$; we call each element of $\mathcal{U}$ a *hitting element*. For the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on $G$, we construct the set system $(\mathcal{U}, \mathcal{S})$ as follows. Let $P$ be any path in [$\mathcal{P}_{{\texttt{vtx}}}$ ]{}and assume w.l.o.g. that it is a [$\llcorner$]{}-type 