=Paper=
{{Paper
|id=Vol-1231/long3
|storemode=property
|title=Graphs of edge-intersecting and non-splitting paths
|pdfUrl=https://ceur-ws.org/Vol-1231/long3.pdf
|volume=Vol-1231
|dblpUrl=https://dblp.org/rec/conf/ictcs/BoyaciESZ14
}}
==Graphs of edge-intersecting and non-splitting paths==
https://ceur-ws.org/Vol-1231/long3.pdf
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