$S$ of paths, define $N[S]:=\cup_{P\in S}N[P]$. We denote the set of neighbours of $P$ that share at least one grid edge with ${\texttt{hPart}}(P)$ (resp., with ${\texttt{vPart}}(P)$) by ${\texttt{hNeighbor}}(P)$ (resp., by ${\texttt{vNeighbor}}(P)$). Throughout this paper, we assume a weak general-position assumption on the corners of paths in [$\mathcal{P}_{{\texttt{edg}}}$ ]{}only: for every two distinct paths $P, P'\in$[$\mathcal{P}_{{\texttt{edg}}}$ ]{}, either $x({\texttt{corner}}(P))\ne x({\texttt{corner}}(P'))$ or $y({\texttt{corner}}(P))\ne y({\texttt{corner}}(P'))$; that is, the corners of no two paths in [$\mathcal{P}_{{\texttt{edg}}}$ ]{}coincide. Notice that by our weak general-position assumption, $\{{\texttt{hNeighbor}}(P), {\texttt{vNeighbor}}(P)\}$ is a partition of $N[P]$ for any $P\in$[$\mathcal{P}_{{\texttt{edg}}}$ ]{}.

Independent Set {#sec:independentSet}
===============

In this section, we consider the [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}problem on [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs, and give an $O(n^3)$-time $O(\log n)$-approximation algorithm for this problem. This improves the previous $O((\log n)^2)$-approximation algorithm of Lahiri et al. [@LahiriMS15]. Our algorithm is actually based on that of Lahiri et al. [@LahiriMS15] and uses a divide-and-conquer approach. We first describe their algorithm and then show how a simple modification can improve the approximation factor, although the running time would slightly increase. For the rest of this section, let $G$ be a [<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 a [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}representation of it.

