The families of Edge Intersection Graphs of Paths in a tree (resp. in a grid) EPT (resp. EPG) are well studied graph classes. Recently we introduced the class of graphs of Edge-Intersecti ng and NonSplitting 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 EdgeIntersecting and Non-Splitting Paths ENP. Although the Edge Intersection 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 coincides with the family of graphs of Edge-Intersecting and N on-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.1
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 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, P i 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 communication 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 [
In [
The motivation to study edge-intersecting and non-splitting paths arises from
all-optical telecommunication networks. In the Wavelength Division M
ultiplexing (WDM) technology different signals can be multiplexed onto a single optical
fiber by using different wavelength ranges of the laser beam [
EPT graphs have been studied in the literature. Their recognition is
NPcomplete [
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 [
Several recent papers consider the edge intersection graphs of paths on a
grid. Since all graphs are EPG (see [
In [
In [
In this work we extend the definition of the family of edge intersecting and nonsplitting 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. 2 2.1
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¯ ⊆ E(G) we denote by G[ V¯ ] and G[ E¯] the subgraphs of G induced by V¯ and by E¯, respectively. The union of two graphs G, G′ is the graph G ∪ G′ d=ef (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 cobipartite 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
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 in INT(P ). If P is open END(P ) d=ef { v0, vℓ} and TAIL(P ) = { (e1, v0), (eℓ, vℓ)} def are the sets of endpoints of P and tails of P , respectively. Given a set P of trails, we define TAIL(P ) d=ef ∪P ∈P TAIL(P ), END(P ) d=ef ∪P ∈P END(P ) and
INT(P ) d=ef ∪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 . Whenever P and P ′ intersect and split(P, P ′) = ∅ we say that P and P ′ are nonsplitting and denote this by P ∼ P ′. Note that in this case all the endpoints 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
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, P i is an ENP representation of G. Two representations are equivalent if they are representations of the same graph. def
Let hH, P i 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: 5 b P2 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, P i. 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 representations of two cliques. Given two vertex disjoint cliques K, K′ of an ENP graph G with a representation hH, P i, we denote S(K, K′) d=ef 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 × P K′ . Then, i) P ∩ P ′ ⊆ ∪S(K, K′), and ii) split(P, P ′) corresponds to the set of all non-terminating segment endpo ints 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. CoB-ipartite * ENP.
Proof. |C n,n| = 2n2 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 |C n,n ∩ ENP| is at most (4n)!((2n + 2s)!)2 ≤ (4n)!((2n + 24n)!)2 = (4n)!(26n)!(26n)!. Therefore, log |C n,n ∩ ENP| = O(n log n), whereas log |C n,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 PP((KK′′)) iwnhtoosaet emxiossttentcweoaorpeegnutarraainlst.eeOdnebyofCtohreoslelaorpye1n. tTrahielssecotnwtoaiendsg(east dleivaisdte) 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. Consider 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 equivalent 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 segments of S(K, K′). Adding the at most 4n busy segments, we conclude that s ≤ 12n. ⊓⊔
Theorem 2. ENP=ENPG Proof. Clearly, ENPG ⊆ ENP. To prove the other direction, consider an ENP graph G with a representation hH, P i. 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 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. 2b ib jb dv b ib 1 b 2 b i b j
b dv b The last step is implied by the following theorem.
Theorem 2.3 [
P′′′ intersect. Moreover a split (e′1′1, v′′, e′1′2), (e′2′1, v′′, e′2′2) of two paths P1′′, P2′′ is mapped to a split (e′1′1′, v′′′, e′1′2′), (e′2′1, v′′′, e′2′2) of the corresponding paths P1′′′, P2′′′ and this mapping is one to one. ⊓⊔ 4
BkE-NPG 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 BkE-NPG 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+1E-NPG that is not Bki E-NPG , 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))E-NPG .
P1
PΠ(1)
P2
PΠ(2)
P3
PΠ(3)
P4
PΠ(4)
PΠ(5)
P6 P5
PΠ(6)
To prove the lower bound, we consider a given number k of bends and we upper bound the number n such that Pmn ∈ BkE-NPG . 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).
Lemma 4. Let K be a complete graph with BkE-NPG representation hH, P i. Then ∪PK contains at most 2 j (3−δ2K)k k 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 of which contains at most k bends. Therefore, ∪PK contains at most 2k = 2 j (3−δ2K)k k 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=∪2PjK(3−isδKa )cklko.sed trail. Therefore the number of bends of ∪PK is at most 2 32k 2 ⊓⊔ Corollary 2. A clique K of a B1E-NPG 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 BkE-NPG representation hH, P i. 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 ∩ BkE-NPG such that |S (K, K′)| = 3k − 6.
Lemma 6. If n > 36k2 + 6k, then Pmn ∈/ BkE-NPG .
Sketch of Proof: Let Pmn = (K, K′, E) and assume by contradiction that Pmn is a BkE-NPG graph with a corresponding ENPG representation hH, P i. Let S = S(K, K′). By Lemma 5, |S| ≤ 3k. Therefore, |S| (4·|S| +2) ≤ 36k2 +6k < n, i.e. n > 4 S|| + 2.
S||
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 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¯ S′ crosses w. All the paths of PK¯ S (resp. PK¯ S′ ) have one endpoint in 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 Pv1 and Pv2 in the 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 E-NPG ( Bki+1E-NPG for i ∈ { 1, 2, . . .} . Proof. Consider the family of BkE-NPG graphs for some integer k ≥ 1, and let G = Pm36k2+6k+1. G ∈/ BkE-NPG by Lemma 6. On the other hand, by Lemma 3, G ∈ B72k2+12kE-NPG . Therefore BkE-NPG ( B72k2+12kE-NPG . 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
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 E-NPG ( Bki+1 E-NPG for every i. In
particular, is B1E-NPG ( B2E-NPG ( · · · ? In [