for this problem on two non-trivial subclasses of [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs. To our knowledge, these are the first results for the [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}problem on [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs, partially answering a question posed by Epstein et al. [@EpsteinGM13].
author:
- Saeed Mehrabi
bibliography:
- 'ref.bib'
title: 'Approximation Algorithms for Independence and Domination on [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}and [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}Graphs'
---

Introduction {#sec:introduction}
============

In this paper, we study [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}and [<span style="font-variant:small-caps;">Minimum Dominating Set</span> ]{}on [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}and [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graphs. These are two special subclasses of *string graphs*, which are of interest in several applications such as circuit layout design and bioinformatics. In a string representation of a graph, the vertices are drawn as a set of curves in the plane and two vertices are adjacent if their corresponding curves intersect; graphs that can be represented in this way are called string graphs. Studying string graphs dates back to 1970s when Ehrlich et al. [@EhrlichET76] showed that every planar graph has a string representation. Also, Scheinerman’s conjecture [@thesisEdwardScheinerman], stating that all planar graphs can be represented as intersection graphs of line segments, was a long-standing open problem until 2009 when it was proved affirmatively 