Graphs of edge-intersecting and non-splitting paths ⋆ Arman Boyacı1, Tınaz Ekim1 , Mordechai Shalom2 , and Shmuel Zaks3 1 Department of Industrial Engineering, Bogazici University, Istanbul, Turkey [arman.boyaci,tinaz.ekim]@boun.edu.tr 2 TelHai College, Upper Galilee, 12210, Israel cmshalom@telhai.ac.il ⋆⋆ 3 Department of Computer Science, Technion, Haifa, Israel. zaks@cs.technion.ac.il Abstract. The families of Edge Intersection Graphs of Paths in a tree (resp. in a grid) EPT (resp. EPG) are well studied graph classes. Re- cently we introduced the class of graphs of Edge-Intersecting and Non- Splitting Paths in a Tree (ENPT) [2]. In this model, two vertices are adjacent if they represent two intersecting paths of a tree whose union is also a path. In this study we generalize this graph class by allowing the host graph to be an arbitrary graph. These are the graphs of Edge- Intersecting and Non-Splitting Paths ENP. Although the Edge Intersec- tion Graphs of Paths in an arbitrary graph includes all graphs, we show that this is not the case for ENP. We also show that the class ENP co- incides with the family of graphs of Edge-Intersecting and Non-Splitting Paths in a Grid (ENPG). Following similar studies for EPG graph class, we study the implications of restricting the number of bends in the grid, of the individual paths. We show that restricting the bend number also restricts the graph class. Specifically, by restricting the number of bends one gets an infinite sequence of classes such that every class is properly included in the next one. 1 Introduction 1.1 Background The intersection graph of a family of sets is a graph in which every vertex corresponds to a set in the family, and two vertices of the graph are adjacent if and only if their corresponding set have a non-empty intersection. It is easy to see that every graph is an intersection graph. Therefore, it makes sense to study intersection graphs only when one focuses on specific families of sets. The family of paths on graphs is a commonly studied family of sets. To distinguish the graph on which the paths are defined, from the resulting intersection graph, this graph ⋆ This work was supported in part by TUBITAK PIA BOSPHORUS Grant No. 111M303. ⋆⋆ Currently in the Department of Industrial Engineering, Bogazici University, Istanbul, Turkey, supported by TUBITAK 2221 Programme. 45 A.Boyacı et al. Graphs of edge-intersecting and non-splitting paths is termed the host graph. Given a host graph H and a set P of paths in H, the Edge Intersection Graph of Paths (EP graph) of P is denoted by Ep(P). Ep(P) contains a vertex for each path in P, and it contains an edge between two vertices if the corresponding two paths intersect in at least one edge. A graph G is EP if there exist a graph H and a set P of paths in H such that G = Ep(P). In this case we say that hH, Pi is an EP representation of G. We also denote by EP the family of all graphs G that are EP. EP graphs have applications in many areas, and in particular in commu- nication networks. Consider a communication network, and routes of messages to be delivered in it. Two paths conflict if they both require the usage of the same link. This conflict model is equivalent to an EP graph. Suppose we try to find a schedule for the messages such that no two messages sharing a link are scheduled at the same time interval. Then a proper vertex coloring of the EP graph corresponds to a feasible schedule on this network. Often the host graphs are restricted to certain families such as paths, cycles, trees, grids, etc. When H is restricted to paths and cycles we get the well known families of interval graphs [11] and circular arc graphs [15], respectively. When H is restricted to trees, we obtain the family of Edge Intersection Graph of Paths in a tree (EPT) [6], and finally when H is a grid, the corresponding graph is termed an EPG graph [10]. In [2] we defined the graph of edge intersecting and non-splitting paths of a tree (ENPT) of a given representation hT, Pi as described above, denoted by Enpt(P). This graph is a subgraph of Ept(P): it has a vertex v for each path Pv of P and two vertices u, v of this graph are adjacent if the paths Pu and Pv edge-intersect and do not split (that is, their union is a path). A graph G is an ENPT graph if there is a tree T and a set of paths P of T such that G = Enpt(P). We note that whenever T is a path Ept(P) = Enpt(P) is an Interval Graph. Therefore, the class ENPT includes all Interval Graphs. In this work we extend this definition to the case where the host graph is not necessarily a tree. The motivation to study edge-intersecting and non-splitting paths arises from all-optical telecommunication networks. In the Wavelength Division Multiplex- ing (WDM) technology different signals can be multiplexed onto a single optical fiber by using different wavelength ranges of the laser beam [13]. A stream of signals traveling from its source to its destination in optical form is termed a lightpath. A lightpath is realized by signals traveling through a series of fibers, on a certain wavelength. Specifically, Wavelength Assignment problems (WLA) are a family of path coloring problems that aim to assign wavelengths (i.e. col- ors) to lightpaths, so that no two lightpaths with a common edge receive the same wavelength and certain objective function (depending on the problem) is minimized. Traffic Grooming is the term used for combination of several low- capacity requests into one lightpath using Time Division Multiplexing (TDM) technology [4]. In this context a set of paths can be combined into one lightpath, thus receiving the same color. One main constraint in traffic grooming is that 46 A.Boyacı et al. Graphs of edge-intersecting and non-splitting paths the union of the paths receiving the same color should constitute a path or a set of disjoint paths, and this originated the study of the class of ENPT graphs. 1.2 Related Work EPT graphs have been studied in the literature. Their recognition is NP- complete [5], whereas one can solve in polynomial time the maximum clique [5] and the maximum stable set [14] problems for this class. Current research on intersection graphs is concentrated on the comparison of various intersection graphs of paths in a tree and their relation to chordal and weakly chordal graphs [7, 8]. The k-edge intersection graphs where two vertices are adjacent if their corresponding paths intersect on at least k edges are studied in [9]. Several recent papers consider the edge intersection graphs of paths on a grid. Since all graphs are EPG (see [10]), studies focus mostly on the sub-classes of EPG where the paths have a limited number of bends. An EPG graph is Bk -EPG if it admits a representation in which every path has at most k bends. The bend number of a graph G is the minimum number k such that G has a Bk -EPG representation. Clearly, a graph is B0 -EPG if and only if it is an interval graph. B1 -EPG graphs are studied in [10] in which every tree is shown to be B1 -EPG, and a characterization of C4 representations is given. In [1] it is shown that there exists an outer-planar graph that is not a B1 -EPG. The recognition problem of B1 -EPG graphs is shown to be NP-complete in [12]. The work [1] investigates the bend number of some special graph classes. In [2] we define the family of ENPT graphs and study their properties; in particular, we study the representations of induced cycles, that turns out to be much more complex than their counterpart in the EPT graphs (discussed in [6]). In [3] we focus on graphs with bend number 1. We show that cycles and trees are B1 -ENPG graphs, that the recognition problem of these graphs in NP-complete in general, and provide a polynomial time recognition algorithm for Co-Bipartite graphs. 1.3 Our Contribution In this work we extend the definition of the family of edge intersecting and non- splitting paths on a tree (ENPT) graphs to the general case in which the host graph is not necessarily a tree. In Section 3 we consider the general case and we show that not every co-bipartite graph is an ENP graph, and that the family of ENP graphs is exactly the family of ENPG graphs. Therefore, it is sufficient to consider ENPG graphs for most of the questions. We thus consider, in Section 4, the effect of restricting the number of bends of the paths, where a bend of a path on a grid is a pair of consecutive edges of the path one of which is vertical and the other is horizontal. We show that restricting the number of bends give rise to an infinite hierarchy of sub-families of ENPG graphs, where every family is properly included in the next family in the hierarchy. 47 A.Boyacı et al. Graphs of edge-intersecting and non-splitting paths 2 Preliminaries 2.1 Graphs, Co-Bipartite Graphs Given a simple graph (no loops or parallel edges) G = (V (G), E(G)) and a vertex v of G, we denote by δG (v) the set of edges of G incident to v, by NG (v) the set consisting of v and its neighbors in G, and by dG (v) = |δG (v)| the degree of v in G. Whenever there is no ambiguity we omit the subscript G and write d(v), δ(v) and N (v). Two adjacent vertices u, v of G are twins if NG (u) = NG (v). For a graph G, V̄ ⊆ V (G) and Ē ⊆ E(G) we denote by G[V̄ ] and G[Ē] the subgraphs of G induced by V̄ and by Ē, respectively. The union of two graphs G, G′ is the def graph G ∪ G′ = (V (G) ∪ V (G′ ), E(G) ∪ E(G′ )). We emphasize that two graphs G and G′ are equal if and only if V (G) = V (G′ ) and E(G) = E(G′ ). Therefore, two isomorphic graphs may be distinct, and they are considered as such in the counting arguments in our proofs. A graph G = (V, E) is co-bipartite if V can be partitioned into two cliques. Note that this partition is not necessarily unique. We denote bipartite and co- bipartite graphs as triples (V1 , V2 , E) where a) V1 ∩ V2 = ∅, b) for bipartite graphs V1 and V2 are independent sets, c) for co-bipartite graphs V1 and V2 are cliques, d) E ⊆ V1 × V2 (in other words E does not contain the cliques’ edges). Unless stated otherwise we assume that G is connected and none of V1 , V2 is empty. 2.2 Walks, trails, paths, segments, splits A walk in a graph G = (V (G), E(G)) is a sequence P = (e1 , e2 , . . . , eℓ ) of edges of E(G) such that there are vertices v0 , v1 , . . . , vℓ satisfying ei = {vi−1 , vi } for every i ∈ [ℓ]. Clearly, the reverse sequence (eℓ , . . . , e1 ) is also a walk. The length of P is the number ℓ of (not necessarily distinct) edges in the sequence. In this work we do not consider trivial (zero length) walks, as such walks do not intersect others. P is closed whenever v0 = vℓ , and open otherwise. A trail is a walk consisting of distinct edges. A (simple) path is a walk consisting of distinct vertices except possibly v0 = vℓ . A contiguous sub-sequence of a walk (resp. trail, path) is termed a sub-walk (resp. sub-trail, sub-path). Let P = (e1 , e2 , . . . , eℓ ) be a trail with vertices v0 , v1 , . . . , vℓ as above. For every i ∈ [ℓ − 1], the triple (ei , vi , ei+1 ) is an internal point of P . Whenever P is closed, the triple (eℓ , vℓ = v0 , e1 ) too, is an internal point of P . We denote the set of internal points of P by INT(P ). We say that a vertex v is an internal vertex of P , or equivalently that P crosses v if v is in (i.e. is the second entry of) a triple def def in INT(P ). If P is open END(P ) = {v0 , vℓ } and TAIL(P ) = {(e1 , v0 ), (eℓ , vℓ )} are the sets of endpoints of P and tails of P , respectively. Given a set P of def def trails, we define TAIL(P) = ∪P ∈P TAIL(P ), END(P) = ∪P ∈P END(P ) and 48 A.Boyacı et al. Graphs of edge-intersecting and non-splitting paths def INT(P) = ∪P ∈P INT(P ). For brevity, in the text we often refer to internal points as vertices and to tails as edges. Moreover, when we apply the intersection and union operations on two trails we consider them as sets of internal points and endpoints. Given two trails P = (e1 , e2 , . . . , eℓ ) and P ′ = (e′1 , e′2 , . . . , e′ℓ′ ), a segment of P ∩ P ′ is a maximal trail that constitutes a sub-trail of both P and P ′ . Since P and P ′ are trails, P ∩ P ′ is the union of edge disjoint segments. We denote this set by S(P, P ′ ). A tail (resp. endpoint) of a segment is terminating if it is in TAIL(P, P ′ ) (resp. END(P, P ′ )). A split of P and P ′ is a pair of internal points (ei , vi , ei+1 ), (e′j , vj′ , e′j+1 ) ∈ INT(P ) × INT(P ′ ) such that vi = vj′  and {ei , ei+1 } ∩ e′j , e′j+1 = 1. Note that the common edge and the common vertex constitute a non-terminating tail of a segment of P ∩ P ′ and conversely every non-terminating tail of a segment corresponds to a split. We denote by split(P, P ′ ) the set of all splits of P and P ′ , which corresponds to the set of all non-terminating tails of the segments S(P, P ′ ). P k P ′ denotes that P and P ′ are non-intersecting, i.e. edge-disjoint. When- ever P and P ′ intersect and split(P, P ′ ) = ∅ we say that P and P ′ are non- splitting and denote this by P ∼ P ′ . Note that in this case all the end- points of the segments are terminating. As there are at most 4 such endpoints 1 ≤ |S(P, P ′ )| ≤ 2. Moreover, in this case P ∪ P ′ is a trail. When split(P, P ′ ) 6= ∅ we say that P and P ′ are splitting and denote this by P ≁ P ′ . Clearly, for any two paths P and P ′ exactly one of the following holds: P k P ′ , P ∼ P ′ , P ≁ P ′ . See Figure 1 for an example. A bend of a trail P in a grid H is an internal point of P whose edges have different directions, i.e. one vertical and one horizontal. 2.3 The EP and ENP graph families Let P be a set of trails in a graph H. The graphs Ep(P) and Enp(P) are such that V (Enp(P)) = V (Ep(P)) = V and there is a one to one correspondence between P and V , i.e. P = {Pv : v ∈ V }. Given two trails Pu , Pv ∈ P, {u, v} is an edge of Ep(P) if and only if Pu and Pv have a common edge. Moreover, {u, v} is an edge of Enp(P) if and only if Pu ∼ Pv . Clearly, E(Enp(P)) ⊆ E(Ep(P)). A graph G is ENP if there is a graph H and a set of paths P of H such that G = Enp(P). In this case hH, Pi is an ENP representation of G. Two representations are equivalent if they are representations of the same graph. def Let hH, Pi be a representation of an ENP graph G. Pe = {P ∈ P| e ∈ P } denotes the set of trails of P containing the edge e of H. For a subset S ⊆ V (G) def we define PS = {Pv ∈ P : v ∈ S}. When H is a tree (resp. grid) Ep(P) is an EPT (resp. EPG) graph, and Enp(P) is an ENPT (resp. ENPG) graph; these graphs are denoted also as Ept(P), Epg(P), Enpt(P) and Enpg(P). Unless otherwise stated, without loss of generality we assume that H is a complete graph, as any non-edge of H can be substituted with an edge without affecting Enp(P). Lemma 1. Let K be a clique of an ENP graph. Then one of the following holds: 49 A.Boyacı et al. Graphs of edge-intersecting and non-splitting paths b P1 15 P4 b b b b b b b b 6 7 8 9 10 11 12 13 5 b b 14 P3 P2 b b b 4 1 2 3 b Fig. 1: The pairs of paths (P2 , P4 ) and (P3 , P4 ) do not share a common edge, therefore P2 k P4 and P3 k P4 . P1 and P4 have a common edge {11, 12}, and 12 is a common internal vertex constituting a split of P1 and P4 , therefore P1 ≁ P4 . Similarly P1 and P3 have three common edges and 10 is a split vertex of P1 and P3 , therefore P1 ≁ P3 . P1 and P2 have three common edges but no splits, then P1 ∼ P2 . The same holds for the pair (P2 , P3 ). However, we note that in the latter case the common edges are separated into two segments. The vertex 8 is not a split point of P1 and P2 because the only internal points of P1 involving this vertex are (e7,8 , 8, e7,9 ), (e14,8 , 8, e8,15 ), and the only internal point of P2 involving it is (e7,8 , 8, e7,9 ). Moreover, |{e7,8 , e7,9 } ∩ {e7,8 , e7,9 }| = 2 6= 1 and |{e7,8 , e7,9 } ∩ {e14,8 , e7,15 }| = 0 6= 1. 50 A.Boyacı et al. Graphs of edge-intersecting and non-splitting paths i) ∪PK is an open trail and ∩PK 6= ∅. ii) ∪PK is a closed trail, and for every edge e of ∪PK there exists an edge e′ of ∪PK such that P ∩ {e, e′ } 6= ∅ for every path P ∈ PK . Proof. If ∪PK contains two internal points (e1 , v, e2 ) and (e′1 , v, e′2 ) such that |{e1 , e2 } ∩ {e′1 , e′2 }| = 1. Then there are two paths P, P ′ ∈ PK such that (e1 , v, e2 ) ∈ INT(P ) and (e′1 , v, e′2 ) ∈ INT(P ′ ). Therefore split(P, P ′ ) 6= ∅ and P ≁ P ′ contradicting the fact that K is a clique. Therefore ∪PK s a disjoint union of trails. However, if ∪PK contains two disjoint trails, then P k P ′ for any two paths P, P ′ from two distinct trails of ∪ppK , contradicting the fact that K is a clique. Therefore ∪PK is one trail. i) If ∪PK is an open trail, then we can embed it on the real line, so that the individual paths of PK are intervals on the real line. Then, the result follows from the Helly property of intervals. ii) If ∪PK is an open trail, let e be any edge of this trail. Let Pe be the set of trails in PK containing the edge e. Then ∪(PK \ Pe ) is an open trail. By the previous result there is an edge e′ of this trail that is contained of all these paths. Therefore, all the paths of PK contain either e or e′ . ⊓ ⊔ Based on this lemma we say that K is an open (resp. closed ) clique if ∪PK is an open (resp. closed) trail. It will be convenient to use the following corollary of Lemma 1 in order to unify the two cases into one. Corollary 1. Let K be a clique of an ENP graph, with a representation hH, Pi. Then ∪PK is a sub-trail of a closed trail in which for every edge e there exists an edge e′ such that P ∩ {e, e′ } 6= ∅ for every P ∈ PK . We denote a closed trail whose existence is guaranteed by Corollary 1 as P (K) . Note that P (K) consists of at most one edge more than ∪PK 3 ENP In this section we show that a) the family of ENP graphs does not include all co-bipartite graphs(Theorem 1), and b) the family of ENP graphs coincides with the family of ENPG graphs (Theorem 2). We proceed with definitions regarding the relationship between the repre- sentations of two cliques. Given two vertex disjoint cliques K, K ′ of an ENP def ′ graph G with a representation hH, Pi, we denote S(K, K ′ ) = S(P (K) , P (K ) ). A segment S ∈ S(K, K ′ ) is quiet in K if does not contain tails of paths of PK , and busy in K, otherwise. The importance of segments stems from the following observation: Observation 31 Consider a pair of trails (P, P ′ ) ∈ PK × PK ′ . Then, i) P ∩ P ′ ⊆ ∪S(K, K ′ ), and 51 A.Boyacı et al. Graphs of edge-intersecting and non-splitting paths ii) split(P, P ′ ) corresponds to the set of all non-terminating segment endpoints crossed by both P and P ′ . Cn,n is the set of all co-bipartite graphs G(K, K ′ , E) where K = [n] and K = {i′ : i ∈ [n]}. The following lemma bounds the number of graphs of this ′ form as a function of the number of segments. Lemma 2. For any s ≥ 0, the number of graphs G = (K, K ′ , E) ∈ Cn,n with a representation hH, Pi such that |S(K, K ′ )| ≤ s is at most (4n)!((2n + 2s)!)2 . Theorem 1. Co-Bipartite * ENP. 2 Proof. |Cn,n | = 2n because there are n2 pairs of vertices (v, v ′ ) ∈ K × K ′ , and for every such pair, either (v, v ′ ) ∈ E or (v, v ′ ) ∈ / E. In the rest of the proof we show that every G ∈ Cn,n has a representation hH ′ , P ′ i for which s = |S(K, K ′ )| ≤ 12n. By Lemma 2, the number of such representations and therefore |Cn,n ∩ ENP| is at most (4n)!((2n + 2s)!)2 ≤ (4n)!((2n + 24n)!)2 = (4n)!(26n)!(26n)!. Therefore, log |Cn,n ∩ ENP| = O(n log n), whereas log |Cn,n | = n2 concluding the proof. It remains to show that G has a representation with s ≤ 12n segments. The number of busy segments of S(K, K ′ ) is at most 4n, because |END(PK )| = 2n and an endpoint can be in at most 2 segments. We now bound the number of quiet segments of S(K, K ′ ). Consider two endpoints from END(PK ) that are consecutive on P (K) and let P be the sub-trail of P (K) between these two endpoints. By this choice, every trail of PK intersecting P includes P . Let S̄ be the set of segments S that are sub-trails of P (thus V (S) ⊆ INT(P )). Suppose that S̄ > 4. Consider the two edges ea′ and eb′ of ′ P (K ) whose existence are guaranteed by Corollary 1. These two edges divide ′ P (K ) into at most two open trails. One of these open trails contains (at least) 3 segments S1 , S2 , S3 ∈ S̄ where the indices are in the order they appear on this open trail from ea′ to eb′ (see Figure 2). Let also vi1 , vi2 be the endpoints of Si in the same order. We claim that the representation obtained by adding to H a new vertex x and two edges {v21 , x} , {x, v22 } and finally modifying all the trails intersecting P (that therefore include S2 ) so that the segment S2 is replaced by the trail ({v21 , x} , {x, v22 }) is an equivalent representation. Clearly, any trail that does not intersect S2 is not affected by this modification. Con- sider two trails Pv and Pv′ such that (v, v ′ ) ∈ K × K ′ and both intersect S2 . Pv includes P and therefore includes all the vertices of S2 , in particular crosses v21 and v22 . On the other hand, by Corollary 1, Pv′ contains at least one of ea′ and eb′ . Without loss of generality let eb′ ∈ Pv′ . Then, v22 is an internal vertex of Pv′ . We conclude that v22 ∈ split(Pv , Pv′ ), i.e. (v, v ′ ) ∈ / E(G). After the modification, we have v31 ∈ split(Pv , Pv′ ), thus (v, v ′ ) is not an edge of the resulting graph. Therefore, the new representation is equivalent to hH, Pi. After this modification, S is not a segment of S(K, K ′ ) and the new representation has one segment less. We can apply this transformation until we get an equiva- lent representation hH ′ , P ′ i having at most 4 quiet segments between every two consecutive vertices of END(PK ). In other words, hH ′ , P ′ i has at most 8n quiet 52 A.Boyacı et al. Graphs of edge-intersecting and non-splitting paths segments of S(K, K ′ ). Adding the at most 4n busy segments, we conclude that s ≤ 12n. ⊓ ⊔ x b Pv b b v21 S2 v22 v12 S1 v31 v11 S3 v32 b b b ea′ eb′ b Pv′ Fig. 2: Getting a representation with at most 8n quiet segments in the proof of Theorem 1. Whenever there are 3 segments on one side of the closed trail, the middle one can be bypassed. Theorem 2. ENP=ENPG Proof. Clearly, ENPG ⊆ ENP. To prove the other direction, consider an ENP graph G with a representation hH, Pi. We transform this representation into an equivalent ENPG representation, in three steps. In the first step, we obtain an equivalent representation hH ′ , P ′ i where H ′ is planar. In the second step, we transform hH ′ , P ′ i to an equivalent representation hH ′′ , P ′′ i where H ′′ is planar and ∆(H ′′ ) ≤ 4. Finally, we transform hH ′′ , P ′′ i to an ENPG representation. The host graph H can be embedded in a plane such that the vertices are mapped to a set of points in general position on the plane and the edges are drawn as straight line segments. Specifically, no three points are co-linear and no three segments intersect at one point. Note that the mapping of the edges might intersect, however as the points are in general position, we can assume that no three edges intersect at the same point. For every intersection point of two edges e, e′ , we can add a vertex v to H and subdivide the edges e and e′ (and consequently the paths in P containing e and e′ ) such that the resulting 4 edges are incident to v. Every pair of paths P, P ′ that include e and e′ respectively now intersect at v. However as we are not concerned with vertex intersections, the resulting representation is a representation of G. We continue in this way until 53 A.Boyacı et al. Graphs of edge-intersecting and non-splitting paths all intersection points are replaced by a vertex. The graph H ′ of the resulting representation hH ′ , P ′ i is clearly planar. We now transform the representation hH ′ , P ′ i to a representation hH ′′ , P ′′ i where H ′′ is planar with maximum degree at most 4. We start with hH ′′ , P ′′ i = hH ′ , P ′ i, and as long as there is a vertex v with dH ′′ (v) > 4, we eliminate such a vertex without introducing new vertices of degree more than 4 using the following procedure described in Figure 3: we number the edges incident to v as e1 , e2 , . . . , edv in counterclockwise order according to the planar embedding of H ′ . Then e1 and edv are in the same face F of H ′′ . We replace the vertex v with a path of dv vertices v1 , v2 , . . . , vdv such that each edges ei is incident to vi . Clearly, the constructed path is part of F . We now construct the gadget in Figure 3 within the face F , where every path crossing v from an edge ei to another edge ej with i < j is modified as described in the figure. Clearly, we do not lose intersections in this process. On the other hand, every pair of paths that intersect within the gadget have at least one edge incident to v in common before the transformation. Moreover, two paths have a split vertex within the gadget if and only if they split at v before the transformation. 1 2 i j dv b b b b b b 1 i 2 1 b b 2 b b b b b i b b b ei b b v j b b b b ej b b j dv dv b Fig. 3: The gadget used in the second transformation in the proof of Theorem 2 The last step is implied by the following theorem. Theorem 2.3 [16]: A planar graph H ′′ with maximum degree at most 4 can be embedded in a grid graph H ′′′ of polynomial size: the vertices u′′ of H ′′ are mapped to vertices u′′′ of H ′′′ ; each edge e′′ = {u′′ , v ′′ } of H ′′ is mapped to a path e′′′ between u′′′ and v ′′′ in H ′′′ ; the intermediate vertices of e′′′ belong to exactly one such path. Given an embedding of H ′′ guaranteed by the theorem, we embed every trail P ′′ ∈ P ′′ to a trail P ′′′ of H ′′′ by embedding every edge e′′ of it to the corresponding path e′′′ of H ′′′ . P ′′′ is clearly a walk. P ′′′ a trail, because otherwise there is an edge of H ′′′ that is contained in the embedding of two distinct edges of H ′′ , contradicting the last guarantee of the theorem. Clearly two trails P1′′ , P2′′ of P ′′ intersect if and only if the corresponding paths P1′′′ , P2′′′ in 54 A.Boyacı et al. Graphs of edge-intersecting and non-splitting paths P ′′′ intersect. Moreover a split (e′′11 , v ′′ , e′′12 ), (e′′21 , v ′′ , e′′22 ) of two paths P1′′ , P2′′ is mapped to a split (e′′′ ′′′ ′′′ ′′ ′′′ ′′ 11 , v , e12 ), (e21 , v , e22 ) of the corresponding paths P1 , P2 ′′′ ′′′ and this mapping is one to one. ⊓ ⊔ 4 Bk -ENPG In this section we investigate the effect of restricting the number of bends of the paths on the family of ENPG graphs. An ENPG graph is Bk -ENPG if it has an ENPG representation hH, Pi, in which every path P ∈ P has at most k bends. The graph Pmn ∈ Cn,n is the co-bipartite graph (V, V ′ , E) with |V | = |V ′ | = n and E constitutes a perfect matching. In what follows we present upper and lower bounds for the bend number of this graph depending on n (lemmata 3 and 6). Using these bounds we show in Theorem 3 that for some infinite and increasing sequence of numbers k1 , k2 , . . . there is a graph in Bki+1 -ENPG that is not Bki -ENPG, thus proving the existence of an infinite hierarchy within the family of ENPG graphs. The following upper bound whose proof can be found in the appendix is implied by the representation in Figure 4. Lemma 3. Pmn ∈ B(2(n−1)) -ENPG. P6 P5 PΠ(6) P4 PΠ(5) P3 PΠ(4) P2 PΠ(3) P1 PΠ(2) PΠ(1) Fig. 4: The ENPG representation of the graph Pmn with 2(n − 1) bends (proof of Lemma 3) To prove the lower bound, we consider a given number k of bends and we upper bound the number n such that Pmn ∈ Bk -ENPG. We first show that a bound on the number of bends implies a bound on the total number of bends in the representation of a clique (Lemma 4). Then we show that this implies an upper bound on the number of segments (Lemma 5), and finally using this bound we bound n from above (Lemma 6). 55 A.Boyacı et al. Graphs of edge-intersecting and non-splitting paths Lemma 4. Let K be a complete j graph with k Bk -ENPG representation hH, Pi. (3−δK )k Then ∪PK contains at most 2 2 bends, where δK = 1 when K is an open clique and 0 otherwise. Proof. If K is an open clique (δK = 1), then there exists an edge e contained in every P ∈ PK . e divides ∪PK into two trails each j of which k contains at most k (3−δK )k bends. Therefore, ∪PK contains at most 2k = 2 2 bends. If K is a closed clique (δK = 0), consider a trail P = (e1 , . . . , eℓ ) of PK . Let P1 (resp. Pℓ ) be a trail containing e1 (resp. eℓ ) with the maximum number of edges from ∪PK \ P . P ∪ P1 ∪ Pℓ = ∪PK , because otherwise there is an edge e ∈ ∪PK \ {P, P1 , Pℓ } that is included in some trail P ′ that does not contain neither e1 nor eℓ , i.e. does not intersect P , contradicting the fact that K is a clique. We conclude that the number of bends of ∪PK is at most 3k. Moreover, this number is even because ∪PjK is a closed k trail. Therefore the number of bends of ∪PK is at most  3k  (3−δK )k 2 2 =2 2 . ⊓ ⊔ Corollary 2. A clique K of a B1 -ENPG graph is an open clique and ∪PK has at most 2 bends. In the appendix we prove the following lemma Lemma 5. Let G = (K, K ′ , E) ∈ Cn,n with a Bk -ENPG representation hH, Pi. Then i) |S(K, K ′ )| ≤ 3k. ii) Moreover, this upper bound is asymptotically tight: there exist infinitely many pairs k, n with a graph G ∈ Cn,n ∩ Bk -ENPG such that |S(K, K ′ )| = 3k − 6. Lemma 6. If n > 36k 2 + 6k, then Pmn ∈ / Bk -ENPG. Sketch of Proof: Let Pmn = (K, K ′ , E) and assume by contradiction that Pmn is a Bk -ENPG graph with a corresponding ENPG representation hH, Pi. Let S = S(K, K ′ ). By Lemma 5, |S| ≤ 3k. Therefore, |S| (4·|S|+2) ≤ 36k 2 +6k < n, n i.e. |S| > 4 |S| + 2. For an edge e = (v, v ′ ) ∈ E we say that e is realized in segment S ∈ S if Pv ∩Pv′ ∩S 6= ∅. Every edge e = (v, v ′ ) is realized in at least one segment, because otherwise Pv ∩ Pv′ = ∅, contradicting the fact that (v, v ′ ) ∈ E. As |E| = n, there is at least one segment S in which ℓ ≥ n/ |S| > 4 · |S| + 2 edges are realized. As E is a perfect matching, these ℓ edges ES ⊆ E constitute a perfect matching of the subgraph GS = (KS , KS′ , ES ) = Pmℓ induced by all the endpoints of ES . We first show that there is at most one path of PKS crossing both endpoints of S. Assume by contradiction that there are two paths Pu , Pv ∈ PKS crossing both endpoints of S. Let u′ be the unique neighbor of u in KS′ . Then Pu′ ⊆ S because otherwise Pu′ splits from Pu . Therefore, Pv ⊇ S ⊇ Pu′ , i.e. Pv ∼ Pu′ and (v, u′ ) ∈ ES , contradicting the fact that GS = Pmℓ . Similarly, there is at most one path from PKS′ crossing both endpoints of S. We conclude that GS 56 A.Boyacı et al. Graphs of edge-intersecting and non-splitting paths contains a subgraph G¯S = (K¯S , K¯S′ , E¯S ) = Pmℓ̄ where ℓ̄ ≥ ℓ − 2 > 4 · |S| with a representation in which every path crosses at most one endpoint of S. Consider an edge e = (v, v ′ ) of G¯S . Pv and Pv′ do not cross the same endpoint of S, as otherwise they would split. Let w, w′ be the endpoints of S. There is a set E¯S of ℓ̄¯ ≥ ℓ̄/2 > 2 · |S| edges such that their endpoints induce a graph G¯S = (K¯S , K¯S′ , E¯S ) = Pmℓ̄¯, where no path Pv ∈ PK¯S crosses w′ and no path Pv′ ∈ PK¯′ crosses w. All the paths of PK¯S (resp. PK¯′ ) have one endpoint in S S INT(S). The other endpoint of such a path can be in one of the |S| segments, or between two of them. We classify the paths of PK¯S by the location of the other endpoint. As ℓ̄¯ > 2 · |S|, there are at least two paths P and P in the v1 v2 same category, i.e. crossing exactly the same segment endpoints. For i ∈ {1, 2} let Pvi′ be the unique neighbour of vi in K¯S′ . C = (v1 , v2 , v2′ , v1′ ) is a cycle of G = Enpg(P), therefore it is also a cycle of Epg(P). We note that every pair of intersecting paths among these 4 paths intersect also in S. Then C is also a cycle of the interval graph obtained by restricting all the trails of hH, Pi to S. As an interval graph cannot contain an induced C4 , it must contain one chord. Assume without loss of generality that (v1 , v2′ ) is such a chord. By definition, this chord is not in Pmn . We conclude that Pv1 ≁ Pv2′ , implying split(Pv1 , Pv2′ ) 6= ∅. As Pv1 and Pv2 cross exactly the same segment endpoints, we have split(Pv2 , Pv2′ ) = split(Pv1 , Pv2′ ) 6= ∅, contradicting the fact that (v2 , v2′ ) is an edge of G. ⊓ ⊔ We are now ready to prove the main result of this section. Theorem 3. There is an infinite increasing sequence of integers {ki : i = 1, 2, . . .} such that Bki -ENPG ( Bki+1 -ENPG for i ∈ {1, 2, . . .}. Proof. Consider the family of Bk -ENPG graphs for some integer k ≥ 1, and let G = Pm36k2 +6k+1 . G ∈ / Bk -ENPG by Lemma 6. On the other hand, by Lemma 3, G ∈ B72k2 +12k -ENPG. Therefore Bk -ENPG ( B72k2 +12k -ENPG. We conclude that the infinite sequence defined as ki+1 = 72ki2 + 12ki for any i > 1 satisfies the claim where k1 ≥ 0 is chosen arbitrarily. ⊓ ⊔ 5 Summary and Future Work In this work we generalized the family of ENPT graphs to ENP graphs in which the host graphs can be any graph. We showed that without loss of generalization, we can restrict the host graphs to grids. Moreover, this family ENPG does not contain all graphs, as opposed to the family of EPG graphs that contains all graphs. We showed that by restricting the number of bends in the paths, we can define an infinite hierarchy of subfamilies of ENPG. Although most of the results in this work are proved for cobipartite graphs, the counting arguments used in the proofs of Theorem 1 and Lemma 6 can be extended to the more general case of graphs with a large clique number. This extension is work in progress. Another open question is to find the sequence of the smallest numbers ki such that Bki -ENPG ( Bki+1 -ENPG for every i. In particular, is B1 -ENPG ( B2 -ENPG ( · · · ? In [2] we studied recognition 57 A.Boyacı et al. Graphs of edge-intersecting and non-splitting paths problems in given graph pairs, i.e. a pair((Ept(P), Enpt(P)) of graphs that are defined on the same set of vertices. A similar study on EP, ENP graph pairs is another interesting research direction. References 1. T. C. Biedl and M. Stern. On edge-intersection graphs of k-bend paths in grids. Discrete Mathematics & Theoretical Computer Science, 12(1):1–12, 2010. 2. A. Boyacı, T. Ekim, M. Shalom, and S. Zaks. Graphs of edge-intersecting non- splitting paths in a tree: Towards hole representations. In The Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Luebeck, Germany, pages 115–126, June 2013. 3. A. Boyacı, T. Ekim, M. Shalom, and S. Zaks. Graphs of edge-intersecting and non-splitting one bend paths in a grid, 2014. In preparation. 4. O. Gerstel, R. Ramaswami, and G. Sasaki. Cost effective traffic grooming in wdm rings. In INFOCOM’98, Seventeenth Annual Joint Conference of the IEEE Com- puter and Communications Societies, 1998. 5. M. C. Golumbic and R. E. Jamison. Edge and vertex intersection of paths in a tree. Discrete Mathematics, 55(2):151 – 159, 1985. 6. M. C. Golumbic and R. E. Jamison. The edge intersection graphs of paths in a tree. Journal of Combinatorial Theory, Series B, 38(1):8 – 22, 1985. 7. M. C. Golumbic, M. Lipshteyn, and M. Stern. Equivalences and the complete hierarchy of intersection graphs of paths in a tree. Discrete Appl. Math., 156:3203– 3215, Oct. 2008. 8. M. C. Golumbic, M. Lipshteyn, and M. Stern. Representing edge intersection graphs of paths on degree 4 trees. Discrete Mathematics, 308(8):1381–1387, 2008. 9. M. C. Golumbic, M. Lipshteyn, and M. Stern. The k-edge intersection graphs of paths in a tree. Discrete Appl. Math., 156:451–461, Feb. 2008. 10. M. C. Golumbic, M. Lipshteyn, and M. Stern. Edge intersection graphs of single bend paths on a grid. Networks, 54(3):130–138, 2009. 11. A. Hajnal and J. Surányi. Über die auflösung von graphen in vollständige teil- graphen. Ann. Univ. Sci. Budapest Eötrös Sect. Math., 1:113–121, 1958. 12. D. Heldt, K. Knauer, and T. Ueckerdt. Edge-intersection graphs of grid paths: the bend-number. Discrete Applied Mathematics, 2013. 13. R. Ramaswami, K. N. Sivarajan, and G. H. Sasaki. Optical Networks: A Practical Perspective. Morgan Kaufmann Publisher Inc., San Francisco, 3rd edition, August 2009. 14. R. E. Tarjan. Decomposition by clique separators. Discrete Mathematics, 55(2):221 – 232, 1985. 15. A. Tucker. Characterizing circular-arc graphs. Bulletin of the American Mathe- matical Society, 76(6):1257–1260, 11 1970. 16. L. Yanpei, A. Morgana, and B. Simeone. General theoretical results on rectilinear embedability of graphs. Acta Mathematicae Applicatae Sinica, 7:187192, 1991. 58