Title: Approximation Algorithms for Independence and Domination on B$_1$-VPG and B$_1$-EPG Graphs,
Abstract: A graph $G$ is called B$_k$-VPG (resp., B$_k$-EPG), for some constant $k\geq
0$, if it has a string representation on a grid such that each vertex is an
orthogonal path with at most $k$ bends and two vertices are adjacent in $G$ if
and only if the corresponding strings intersect (resp., the corresponding
strings share at least one grid edge). If two adjacent strings of a B$_k$-VPG
graph intersect exactly once, then the graph is called a one-string B$_k$-VPG
graph.
In this paper, we study the Maximum Independent Set and Minimum Dominating
Set problems on B$_1$-VPG and B$_1$-EPG graphs. We first give a simple $O(\log
n)$-approximation algorithm for the Maximum Independent Set problem on
B$_1$-VPG graphs, improving the previous $O((\log n)^2)$-approximation
algorithm of Lahiri et al. (COCOA 2015). Then, we consider the Minimum
Dominating Set problem. We give an $O(1)$-approximation algorithm for this
problem on one-string B$_1$-VPG graphs, providing the first constant-factor
approximation algorithm for this problem. Moreover, we show that the Minimum
Dominating Set problem is APX-hard on B$_1$-EPG graphs, ruling out the
possibility of a PTAS unless P=NP. Finally, we give constant-factor
approximation algorithms for this problem on two non-trivial subclasses of
B$_1$-EPG graphs. To our knowledge, these are the first results for the Minimum
Dominating Set problem on B$_1$-EPG graphs, partially answering a question
posed by Epstein et al. (WADS 2013).