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.
Let us now consider graphs with small number of bends. Notice first that @math -EPG graphs coincide with interval graphs. Several recent papers started the study EPG graphs with small number of bends. For example, it has been proved that @math -EPG contains trees @cite_5 , and that @math -EPG and @math -EPG respectively contain outerplanar graphs and planar graphs @cite_11 . We can also mention that the recognition of @math -EPG graphs is NP-hard, even when only one shape of path is allowed @cite_6 .
@cite_5 @cite_6 @cite_11
2023033525 2569784685 2065527713 2052977033
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 Abstract In this paper we continue the study of the edge intersection graphs of single bend paths on a rectangular grid (i.e., the edge intersection graphs where each vertex is represented by one of the following shapes: ⌞ , ⌜ , ⌟ , ⌝ ). These graphs, called B 1 - EPG graphs, were first introduced by (2009) [Golumbic, M. C., M. Lipshteyn and M. Stern, Edge intersection graphs of single bend paths on a grid , Networks 54 :3 (2009), 130–138]. We focus on the class [⌞] (the edge intersection graphs of ⌞-shapes) and show that testing for membership in [⌞] is NP-complete. We then give a characterization and polytime recognition algorithm for special subclasses of Split ∩ [ ⌞ ] . We also consider the natural subclasses of B 1 -EPG formed by the subsets of the four single bend shapes (i.e., ⌞ , ⌞ , ⌜ , ⌞ , ⌝ , ⌞ , ⌜ , ⌝ – note: all other subsets are isomorphic to these up to 90 degree rotation). We observe the expected strict inclusions and incomparability (i.e., [ ⌞ ] ⊊ [ ⌞ , ⌜ ] , [ ⌞ , ⌝ ] ⊊ [ ⌞ , ⌜ , ⌝ ] ⊊ B 1 -EPG and [ ⌞ , ⌜ ] is incomparable with [ ⌞ , ⌝ ] ). We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits. Specifically, a graph with property @math is called a @math -graph . If @math satisfies certain properties, then an n-node m-edge @math -graph G can be encoded by a binary string X such that (1) G and X can be obtained from each other in O(n log n) time, and (2) X has at most @math bits for any continuous superadditive function @math so that there are at most @math distinct @math -node @math -graphs. The methodology is applicable to general classes of graphs; this paper focuses on planar graphs. Examples of such @math include all conjunctions over the following groups of properties: (1) G is a planar graph or a plane graph; (2) @math is directed or undirected; (3) @math is triangulated, triconnected, biconnected, merely connected, or not required to be connected; (4) the nodes of G are labeled with labels from @math for @math ; (5) the edges of G are labeled with labels from @math for @math ; and (6) each node (respectively, edge) of G has at most @math self-loops (respectively, @math multiple edges). Moreover, @math and @math are not required to be O(1) for the cases of @math being a plane triangulation. These examples are novel applications of small cycle separators of planar graphs and are the only nontrivial classes of graphs, other than rooted trees, with known polynomial-time information-theoretically optimal coding schemes. Given a planar triangulated graph (PTG) G, the problem of constructing a floor-plan F such that G is the dual of F and the boundary of F is rectangular is studied. It is shown that if only zero-concave rectilinear modules (CRM) (or rectangular modules) and 1-CRM (i.e., L-shaped) are allowed, there are PTGs that do not admit any floor-plan. However, if 2-bend modules (e.g., T-shaped and Z-shaped) are also allowed, then every biconnected PTG admits a floor-plan. Thus, the employment of 2-bend modules is necessary and sufficient for graph dualization floor-planning. A linear-time algorithm for constructing a 2-CRM floor-plan of an arbitrary PTG is proposed.