In this paper we consider the Maximum Independent Set problem (MIS) on @math -EPG graphs. EPG (for Edge intersection graphs of Paths on a Grid) was introduced in edgeintersinglebend as the class of graphs whose vertices can be represented as simple paths on a rectangular grid so that two vertices are adjacent if and only if the corresponding paths share at least one edge of the underlying grid. The restricted class @math -EPG denotes EPG-graphs where every path has at most @math bends. The study of MIS on @math -EPG graphs has been initiated in wadsMIS where authors prove that MIS is NP-complete on @math -EPG graphs, and provide a polynomial @math -approximation. In this article we study the approximability and the fixed parameter tractability of MIS on @math -EPG. We show that there is no PTAS for MIS on @math -EPG unless P @math NP, even if there is only one shape of path, and even if each path has its vertical part or its horizontal part of length at most @math . This is optimal, as we show that if all paths have their horizontal part bounded by a constant, then MIS admits a PTAS. Finally, we show that MIS is FPT in the standard parameterization on @math -EPG restricted to only three shapes of path, and @math -hard on @math -EPG. The status for general @math -EPG (with the four shapes) is left open.
We combine the known notion of the edge intersection graphs of paths in a tree with a VLSI grid layout model to introduce the edge intersection graphs of paths on a grid. Let P be a collection of nontrivial simple paths on a grid G. We define the edge intersection graph EPG(P) of P to have vertices which correspond to the members of P, such that two vertices are adjacent in EPG(P) if the corresponding paths in P share an edge in G. An undirected graph G is called an edge intersection graph of paths on a grid (EPG) if G = EPG(P) for some P and G, and 〈P,G〉 is an EPG representation of G. We prove that every graph is an EPG graph. A turn of a path at a grid point is called a bend. We consider here EPG representations in which every path has at most a single bend, called B1-EPG representations and the corresponding graphs are called B1-EPG graphs. We prove that any tree is a B1-EPG graph. Moreover, we give a structural property that enables one to generate non B1-EPG graphs. Furthermore, we characterize the representation of cliques and chordless 4-cycles in B1-EPG graphs. We also prove that single bend paths on a grid have Strong Helly number 3. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009