{'fraction_non_alphanumeric': 0.06683585240415928, 'fraction_numerical': 0.017562377883082174, 'mean_word_length': 3.4026102432272096, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 23, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Readability of digraphs and bipartite graphs

In the final project paper we consider a graph parameter called readability. Motivation for readability comes from bioinformatics applications. Graphs arising in problems related to genome sequencing are of small readability, which motivates the study of graphs of small readability. We present an algorithm due to Braga and Meidanis, which shows that every digraph is isomorphic to the overlap graph of some set of strings. An upper bound on readability is derived from the algorithm. The readability parameter can also be defined for bipartite graphs; in the final project paper special emphasis is given to the bipartite model. The complexity of computing the readability of a given digraph (or of a given bipartite graph) is unknown. A way for the exact computation of readability is presented using Integer Linear Programming. We also present two approaches for computing upper and lower bounds for readability due to Chikhi at al. Finally, the readability is computed exactly for toroidal and two-dimensional grid graphs and a polynomial time algorithm for constructing an optimal overlap labeling of a given two-dimensional or toroidal grid graph is presented.


Preliminaries
In this final project we study a graph parameter called readability. Suppose we are given a finite set of finite strings C over some alphabet Σ. Let s 1 , s 2 ∈ C. For a positive integer k such that k ≤ min{length(s 1 ), length(s 2 )} we say that s 1 overlaps s 2 by k if the suffix of s 1 of length k equals the prefix of s 2 of length k. Denote by ov(s 1 , s 2 ) the minimum k such that s 1 overlaps s 2 and set ov(s 1 , s 2 ) = 0 if s 1 does not overlap s 2 . Given a set of strings C, we can construct the following directed graph: each string represents one vertex and there is directed edge between two vertices u and v if and only if ov(u, v) > 0. The graph obtained this way is called the overlap graph of set C. Clearly this construction can be done in polynomial time. Now consider the reverse problem: given a directed graph G, find a set of strings C such that G is its overlap graph. The smallest integer k for which there is a set of strings C such that the length of each string in C is at most k and G is the overlap graph of C is called the readability of G and denoted by r(G). Note that the size of the alphabet of strings in C is unrestricted.
In this paper we will review the algorithm for building a set of strings for a given overlap graph presented in [1] and consequently we will show that readability is well defined and derive a (weak) upper bound (Chapter 2). In Chapters 3 and 4 we present an ILP formulation for the exact computation of readability, firstly for balanced bipartite graphs (for which parameter will be introduced in Chapter 3) and then for digraphs.
We also present lower and upper bounds on readability in Chapter 5, given by [3]. In the last chapter, we explore the readability of graphs known as two-dimensional grid graphs and toroidal grid graphs.
Motivation for the readability comes from bioinformatics applications. For example, well known graphs in bioinformatics are overlap graphs where each vertex represents some DNA sequence and two vertices are adjacent if and only if there is an overlap between corresponding sequences. There are several problems that have been studied on such graphs, e.g., the Minimum s-Walk Problem and the De Bruijn Superwalk Problem [8]. The problem of constructing a set of strings of a given (overlap) graph also has an application showing that a certain family of problems, a variation of the so-called Minimum Contig Problems, are NP-hard [1].

Basic definitions and notations
We study readability of finite graphs that can be directed or undirected. We will denote by pre(s, l) the prefix of string s of length l. Similarly, suf(s, l) will denote the suffix of s of length l. A labeling of a graph G is assignment of a string to each vertex of G. The length of a labeling is denoted by len( ) and defined as the maximum length of a string in the image of . An overlap labeling of a digraph D is a labeling of D such that for all pairs u, v of vertices of D, the pair (u, v) is an arc of D if and only if ov( (u), (v)) > 0. We will denote the ith character of the string assigned to some vertex u by u(i). We will now introduce some standard notions in graph theory used to study the readability.
Definition 1.2. The chromatic index χ (G) of an undirected graph G is the minimum number of colors needed to color the edges of G such that no two distinct edges that share an endpoint have the same color. We denote the maximum degree of an undirected graph G with ∆(G). In the case of a digraph G, ∆ + (G) denotes the maximum out-degree and ∆ − (G) denotes the maximum in-degree. All bipartite graphs considered in this final project paper will be assumed given with a bipartition of their vertex set into two independent sets (called parts) and thus denoted by G = (S ∪ T, E), where S and T are parts of G. Definition 1.5. A bipartite graph G = (S ∪ T, E) with parts S and T is called a biclique if for any two vertices u ∈ S and v ∈ T we have uv ∈ E(G).

An upper bound on readability
As stated in introduction, the readability of a digraph is well defined. To be able to prove this and give an upper bound for the readability, we will define the notions of a directed matching and a directed edge coloring.
Definition 2.1. A directed matching of a directed graph G is a set M ⊆ E(G) such that for any two distinct arcs u 1 v 1 ∈ M and u 2 v 2 ∈ M we have u 1 = u 2 and v 1 = v 2 i.e., the tails of the edges have to be different and the heads have to be different.  We follow the proof of Braga and Meidanis [1] and to prove this theorem, we will need the following two theorems.
A proof of Theorem 2.4 can be found in [4]. Proof. Given a directed graph G we construct a bipartite graph H as follows: • for every v ∈ V (G) add two vertices v and v to V (H) Since M i is matching of H, we have that M i is a directed matching in G and since matchings in L were pairwise disjoint we conclude that directed matchings in L = {M 1 , M 2 , . . . , M p } are also pairwise disjoint. Also, since the edge coloring assigns a unique color to each edge, we have that for each edge e ∈ E(H) there exists some i ∈ {1, 2, . . . , p} such that e ∈ M i . This means that L covers all edges of G. Thus, L is a directed edge coloring of G and |L| = p. Now we are ready to prove Theorem 2.3. We propose a constructive proof. The idea is to generate a string of the form pre(v).
where U nique(v) is a character not used before, i.e., not occurring in pre(v) nor suf(v) nor in any other string assigned to vertex u ∈ V (G). This way, the number of different characters that appear in the strings assigned to vertices is bounded from below. In fact, algorithm produces labels on vertices using exactly |V (G)| + |E(G)| characters in total. Figure 1 provides an example of algorithm execution. Firstly, we calculate a Algorithm 1: Construction of an overlap labeling of given digraph G Input: Directed graph G suf(u) = pre(v); 10 I = I + 1; and then we process the edges one by one. The maximal length of string after processing all edges and merging is 5, showing that r(D) ≤ 5 Merging: Finally, to prove that the readability is well defined, we have to prove correctness of Algorithm 1.
Proof of Theorem 2.3. We have to prove few things: First, we will prove that if e = uv ∈ E(G) then there exists a positive integer i such that after the execution of algorithm suf(s u , i) = pre(s v , i). If uv ∈ E(G) then ∃i ∈ {1, 2, . . . , p} s.t. uv ∈ M i since L is a directed edge coloring of G. Thus the edge is processed in steps 7, 8, 9. In step 8 an overlap of positive length is created between partial strings assigned to vertices u and v. In further execution of the algorithm, we only extend suf(u) to the left and only extend pre(v) to the right, which means that this overlapping will exist at the end of the execution of the algorithm. Now, we prove the opposite direction: if there is a positive integer l s.t. suf(s u , l) = pre(s v , l) then uv ∈ E(G). Let i = d + (u) and order the out neighborhood of u as N + (u) = {v 1 , . . . , v i } according to the order in which the edges uv i are processed by the algorithm, meaning that uv 1 is first processed, uv 2 second and so on. Denote by I(u, v i ) the value of I in the algorithm right before the edge uv i is processed. Observe that I(u, v i ) > I(u, v i−1 ) > · · · > I(u, v 1 ) which follows from the definition of the ordering of the vertices in the out neighborhood of u. Since we chose I(u, v i ) as a unique character, it appears exactly once in suf(u) after the execution of the algorithm.
Moreover, I(u, v i ) is the largest character in suf(u). Similarly, since we extend suf(u) only to the left, we conclude that for 1 ≤ i < i, character I(u, v i ) appears exactly once and is the largest among all characters to the right of I(u, v i +1 ). From the other side, let j = d − (v) and order neighborhood N − (v) = {u 1 , . . . , u j } according to the order in which the edges u i v are processed by the algorithm. Similarly as above, one can conclude that largest integer in any prefix pre(v) is one of the unique characters, i.e. of the form I(u j , v) for some j ∈ {1, . . . , j}. Now, if there is a positive integer l such that s = suf(s u , l) = pre(s v , l) then by the above, the largest character in s is of the form I(u, v i ) for some i ∈ {1, 2, . . . , i} and of the form I(u j , v) for some j ∈ {1, 2, . . . , j} and since there is an overlap, they must be the same. Thus, Here, we will prove inductively that ∀u ∈ V (G) and for s u ∈ C we have |s u | ≤ 2 p+1 − 1 where s u denotes a string assigned to vertex u. Denote by size(i) for i ∈ {0, 1, . . . , p} the maximum length of a strings assigned to pre(u) and suf(u) for u ∈ V (G) right after processing all edges from M i . size(0) = 0 since before processing M 1 we have only empty strings. During the processing the edges of M i , the strings pre(v) and suf(v), where v is head or tail of a edge, are modified at most once since M i is directed matching and by definition there is no vertex which is head for two edges and there is no vertex which is tail for two edges. Observe that during processing edge uv ∈ M i we only modify pre(v) by concatenating strings obtained in previous step i − 1. Thus, we have size(i) = 2 · size(i − 1) + 1. We use the above fact and induction on i to prove By the above proof, we have size(p) ≤ 2 p − 1, which means that the maximum length of strings assigned to pre(u) or suf(u) after the execution of the algorithm is at most 2 p − 1 for every vertex u ∈ V (G). Since at the end we concatenate pre(u) and suf(u) with additional letter, we have |s u | ≤ 2 · (2 p − 1) + 1 = 2 p+1 − 1.
. The factor 2 p+1 − 1 appears because we have to iterate through all characters of strings assigned to the vertices and by previous proof . A similar reasoning applies to steps 12, . . . , 15, for which the running time is Summing up everything, we get that the time complexity of the algorithm is given by O(2 p (n + m)).
As we can see, to have the algorithm working correctly we must have that the size of alphabet is at least |V (G)| + |E(G)|. Braga and Meidanis [1] showed that given a directed graph G and an alphabet Σ with at least two different symbols, one can compute a set C of strings over Σ such that the overlap graph of C is G in two steps: 1. Using Algorithm 1 compute a set of strings C written over alphabet Σ s.t. |Σ| = n + m, where the overlap graph of C is G.
2. Map each string of C into another string to obtain a set C .
The maximum length of the string in C is bounded from above by the maximum length of strings in C multiplied by a factor of O(log |Σ | (n + m)).
At the expense of possibly increasing the alphabet size, the algorithm could be modified to produce strings of the same length. In the last steps during concatenation of pre(v) and suf(v) i.e., in step 13, instead of one unique character I, one can add arbitrary many unique characters between pre(v) and suf(v) to achieve desired length. and an integer programming formulation 3

.1 Readability of bipartite graphs
In the first chapter we have seen how the readability is defined for directed graphs. Here, we will define and study the readability of bipartite graphs in order to try to understand behavior of this parameter of digraphs. This is possible at least approximately (see  Observe that we do not request the labeling to be injective, which is not the case for digraphs. Moreover, we only care about overlaps "in one direction", from S to T . This gives us more flexibility in the study of readability. Also, the assumption that the strings assigned to vertices by a labeling are of the equal length is without loss of generality (which is not the case for digraphs, see Chapter 4). The next theorem shows that as long as we are interested in the readability approximately, we can focus our attention to balanced bipartite graphs instead of to digraphs. Theorem 3.2 (Chikhi at al. [3]). There exists a bijection φ : B n×n → D n such that for each graph H ∈ B n×n and G ∈ D n with φ(H) = G the following holds: r(G) < r(D) ≤ 2 · r(G) + 1.
A proof of Theorem 3.2 can be found in [3].

Variables of the ILP
Suppose we are given a balanced bipartite graph G = (S ∪ T, E) and a positive integer r. Consider the following decision problem: does G have readability r(G) ≤ r? To answer this question, we will describe an integer linear program that has a feasible solution if and only if r(G) ≤ r.
For every pair of vertices u ∈ S and v ∈ T and for each i, j ∈ {1, 2, . . . , r} we introduce a binary variable x u,v,i,j which is equal to 1 if the ith character of the string assigned to vertex u is equal to jth character of the string assigned to vertex v and equal to 0 if the above characters are different. Furthermore, for each edge e = uv ∈ E(G) and for each i ∈ {1, 2, . . . , r} we define a binary variable z e,i which is equal to 1 if there is a overlapping of the size i between vertices u and v, i.e., x u,v,i−k+1,k = 1 ∀k ∈ {1, . . . , i}. The variable z e,i is equal to 0 if the above is not true.

Constraints of the ILP
We add the constraints listed below.
• Edge constraints: for each edge e = uv ∈ E(G), u ∈ S and v ∈ T , add the following constraints: • Non-edge constraints: for each u ∈ S and v ∈ T such that uv ∈ E(G) add the following constraints: • Transitivity constraints: for each u, w ∈ S such that u = w and for each v, q ∈ T such that v = q and for each i, j, k, l ∈ {1, . . . , r} add x u,v,i,j + x w,v,k,j + x w,q,k,l − x u,q,i,l ≤ 2 Constraints of the first type ensure that we will have an overlap between adjacent vertices. Constraints of the second type ensure that there is no overlap between nonadjacent vertices. Constraints of the third type (transitivity constraints) we introduce to ensure the following implication: if u(i) = v(j) and v(j) = w(k) and w(k) = q(l) =⇒ u(i) = q(l).

Objective function of the ILP and an example
Since we are looking only for a feasible solution the objective function can be arbitrary, for example the constant 0. Now, we have completed the description of the integer linear program. An example of the defined variables and constraints is given in Figure 2.

Proof of correctness
Theorem 3.3. The above defined integer linear program has a feasible solution if and only if given graph is of the readability at most r.
Proof. ( ⇐= ) Let G = (S ∪ T, E) be a balanced bipartite graph of readability at most r and let S s , T s be a sets of strings with ∀s ∈ S s ∪ T s |s| ≤ r such that the overlap graph of (S s , T s ) is isomorphic to G. We may assume without loss of generality that |s| = r ∀s ∈ S s ∪ T s since if ∃s ∈ S s ∪ T s such that |s| < r we can easily find a sets of strings S s , T s by extending each string of S s ∪ T s with a new characters, such that for every s ∈ S s ∪ T s |s | = r and the overlap graph of (S s , T s ) is isomorphic to G. We have to find an assignment to the variables such that each constraint is , and 0 otherwise. For each edge e = uv ∈ E(G) and for each i ∈ {1, . . . , r} We also need to prove that the edge constraints of the second and third type are satisfied. If 0 is assigned to z e,i for some i ∈ {1, . . . , r} then (r − i + 1) · z e,i ≤ r k=i x u,v,k,k−i+1 since all variables are non-negative. If 1 is assigned to z e,i for some i ∈ {1, . . . , r} then ∀k ∈ {i, . . . r} Edge constraints of the third type are also satisfied: if z e,i = 0 for some i ∈ {1, . . . , r} then ∃k ∈ {i, . . . , r} For each u ∈ S and v ∈ T such that uv ∈ E(G) and for each i ∈ {1, . . . , r} among variables x u,v,k,k−i+1 for k ∈ {i, i + 1, ..., r} there exists at least one variable x u,v,l,l−i+1 for some l ∈ {i, i + 1, ..., r} such that x u,v,l,l−i+1 = 0, otherwise, if all of them are equal to 1, then by the definition of the x-variables, there will be an overlap between vertices u and v which would be contradicting the fact that G is overlap graph of (S s , T s ). Then . . , r}. Since this is true for an arbitrary i, all non-edge constraints are satisfied.
Transitivity constraints are obviously satisfied: if x u,v,i,j = 1 and x w,v,k,j = 1 and x w,q,k,l = 1 then u(i) = v(j) = w(k) = q(l) which means that also x u,q,i,l = 1. Thus In all other cases, when at least one among variables x u,v,i,j , x w,v,j,k , x w,q,k,l is equal to 0, the sum x u,v,i,j + x w,v,j,k + x w,q,k,l is at most 2 and since x u,q,i,l is non-negative variable we conclude x u,v,i,j + x w,v,j,k + x w,q,k,l − x u,q,i,l ≤ 2.
( =⇒ ) Suppose now that our integer linear program has a feasible solution. We want to prove that r(G) ≤ r. Assign a string of length r consisting of null characters i.e., character * , to each vertex u ∈ V (G) and suppose that vertices of S and T are linearly ordered so that we have S = {u 1 , . . . , u n } and T = {v 1 , . . . , v n }. Then iterate over u ∈ {u 1 , u 2 , . . . , u n } and v ∈ {v 1 , v 2 , . . . , v n } and over all indices i, j ∈ {1, . . . , r} and do the following: • if x u,v,i,j = 1 and u(i) = v(j) = * , take a character c not yet used and assign c as the ith character of u and jth character of v We have to prove that the overlap graph of the set of strings obtained this way is isomorphic to G. First, we will prove that such assignment is well defined. To do this, it is enough to prove that u(i) = v(j) and u(i), v(j) = * is impossible, i.e., that the ith character of u and the jth character of v are not both different from each other and from the null character at same time. We want to prove that such a situation leads to a contradiction. Suppose x u,v,i,j = 1 for some tuple u, v, i, j where u ∈ S, v ∈ T and suppose u(i) = v(j) = * and suppose that this occurs for the first time i.e. u, v are minimal. Then, there exist w ∈ S, w < u, k ∈ {1, . . . r} and q ∈ T, q < v, l ∈ {1, . . . , r} such that x u,q,i,l = 1 and x w,v,k,j = 1. Then we have x u,v,i,j + x u,q,i,l + x w,v,k,j − x w,q,k,l ≤ 2 =⇒ x w,q,k,l = 1 since all transitivity constraints are satisfied. This means that it has already happened that two characters are different and the variable denoting their equality is equal to 1. This is the contradiction with assumption that u, v are minimal. Now, choose any edge e = uv ∈ E(G). We want to show that the string assigned to u overlaps the string assigned to v. Since z e,1 + z e,2 + ... + z e,r ≥ 1 is satisfied, there exists .., r} otherwise edge constraints of the second type would not be satisfied. This means that Therefore, u overlaps v. Suppose that for some vertices u ∈ S and v ∈ T uv ∈ E(G).
Then, we have to prove that u does not overlap v. Since all non-edge constraints are satisfied, for each i ∈ {1, . . . , r} there exists some k ∈ {i, i + 1, . . . , r} such that x u,v,k,k−i+1 = 0. This means that in our procedure u(k) and v(k −i+1) will be different since x u,v,k,k−i+1 = 0 which means that there is no overlap of size r − i + 1 between u and v. The above arguments show that G is overlap graph of the constructed set C which completes the proof.

Size of the ILP
Let us compute the number of variables and constraints of the derived ILP for a given balanced bipartite graph G with n vertices on both sides and m edges. We defined variables x u,v,i,j for each pair of vertices u ∈ S and v ∈ T and for each pair of indices over {1, . . . , r}. Thus, we have n · n · r · r = n 2 r 2 x-variables. Also, for each edge e and for each index from the set {1, . . . , r} we defined a variable z e,i which gives us |E(G)| · r z-variables. In total, we have n 2 r 2 + r|E(G)| variables.
For each edge, we defined one constraint consisting of variables z and 2r constraints of the second type. For each non-edge we defined r constraints. We defined one constraint for each u, w ∈ S, v, q ∈ T , with u = w and v = q, and for each i, j, k, l ∈ {1, . . . , r} which gives us n 2 · n 2 ·r 4 . In total, we have (1+2r)m+r(n 2 −m)+ n

An integer programming formulation for digraphs
In the bipartite model, we assumed without loss of generality that if a given graph G is of readability at most r then we can find a sets S s and T s such that each string in S s ∪ T s is of the length exactly r. In the model for digraphs, such assumption would not be without loss of generality. An example for this is given in Figure 3.

Constraints of the ILP
• Edge constraints: for each edge e = uv ∈ A(D) add the following constraints: • Non-edge constraints: for every two vertices u, v ∈ V (D) such that uv ∈ A(D) add the following constraints: • Transitivity constraints: for all pairwise distinct u, v, w ∈ V (D) and for all indices i, j, k ∈ {1, . . . , r} add the following constraints: • t-monotonicity constraints: for all vertices u ∈ V (D) and for all i ∈ {1, . . . , r − 1} add the following: (4.7) • Injectivity constraints: for all distinct vertices u, v ∈ V (D): • Symmetry constraints: for all distinct vertices u, v ∈ V (D) and for all indices i, j ∈ {1, . . . , r}: • Additional constraints: for all vertices u, v ∈ V (D) and for all indices i, j ∈ {1, 2, . . . , r}:

Objective function
We look for a feasible solution of above constraints, so we can define an objective function to be any linear function, for example the constant zero function. 3. The role of injectivity and symmetry constraints is obvious.

(Additional constraints)
The inequalities (4.10) and (4.11) ensure that we do not have overlapping of some length such that it consists of null characters.

Bounds on readability
In Chapter 2 we have presented an upper bound for readability for an arbitrary directed graph G is given by 2 p+1 − 1 where p = max{∆ + (G), ∆ − (G)}. This bound can be very weak. For example, for the complete bipartite graph G with n we get r(G) ≤ 2 n+1 − 1 while the readability of G is 1. An overlap labeling of length 1 is obtained by assigning the same character to each vertex. In this chapter we present lower and upper bounds for the readability of bipartite graphs using characterizations given below as well as characterization of the graphs of readability at most 2.

Graphs of readability at most 2
In this section we will present graph theoretic characterizations of the graphs with readability 1 or 2 following Kratsch et al. [2].
between any two vertices u ∈ S i and v ∈ T i so it must hold that there is an edge between any two of them. From the construction of graphs G i it is clear that any vertex u ∈ S is contained in exactly one S i for some i ∈ {1, . . . , k} since (u) = a i .
The same argument we can apply for vertices in T . Combining the above, we get That way we made an overlap between any two vertices that belong to G i . Since G is the disjoint union of G i s there are no edges between G i and G j in G for i = j and also by the above construction there is no overlap since a i = a j for i = j. Thus, such assignment is an overlap labeling of length 1, which completes the proof.
Using the above characterization one can find a polynomial time algorithm to recognize whether a bipartite graph has readability 1. An example is given in Figure 1. In order to state the characterization of bipartite graphs with readability at most 2 we need to introduce the following definitions.  The condition that G must be twin-free graph is not necessary. The proof for that is a simple corollary of Lemma 5.5.

Lower and upper bounds on readability
In order to give lower bound for the readability of bipartite graphs, we introduce a graph parameter distinctness. Note that the distinctness of a given bipartite graph can be computed in polynomial time.
Using the above theorem, it is shown in [3] that there exist graphs of readability at least linear in the number of vertices. The bipartite graph G = (S ∪ T, E) with 2 n − 1 vertices on both sides with this property is obtained by the following rules: Combining this argument with Theorem 5.7 we get the desired conclusion. These graphs are interesting since for any positive integer r one can construct a bipartite graph of readability at least r (although, this can be done more easily also with trees [3]).
We now introduce the notions of decomposition of a bipartite graph and the hierarchial-union-of-bicliques rule (shortly HUB-rule) for a decomposition (and consequently the HUB-number of a bipartite graph) in order to be able to improve upper bound given by Braga and Meidanis [1]. The rule is introduced in the paper [3]. Also, we will use these notions to explore the readability of some special graphs.  In what follows, if a decomposition w is clear from the context, we will usually write G i instead of G w i . An example of a decomposition of a bipartite graph G that satisfies the HUB-rule is any w : E(G) → {1, . . . , k} such that G w 1 , defined as above, is a disjoint union of bicliques and E w 2 , . . . E w k are matchings in G. This is true since by definition G w 1 is a disjoint union of bicliques and since E w 2 , . . . , E w k are matchings in G then there are no pairs of twin vertices. This example is the main motivation for exploring the readability of grid graphs introduced in Chapter 7.

Consequently, one can define graphs
Consider now a bipartite graph G = (S ∪ T, E) and an overlap labeling of G.
Then one can define decomposition w such that for any edge e = uv ∈ E(G), w(e) = ov( (u), (v)). Clearly, w is well defined. The decomposition obtained this way will be called -decomposition. The next theorem gives a connection between -decompositions of G and the HUB-rule: Theorem 5.10. Let be an overlap labeling of a bipartite graph G = (S ∪T, E). Then, the -decomposition satisfies the HUB-rule.
A proof of Theorem 5.10 can be found in [3]. It is easy to see that the -decomposition given in Figure 7 satisfies the HUB-rule (in fact, it satisfies the conditions stated in the paragraph following Definition 5.9). Figure 6 provides an example of a decomposition that does not satisfy the HUB-rule: clearly, each of the graphs G 1 , G 2 , G 3 is a disjoint union of bicliques but, vertices u 1 and u 2 are twins in G 2 and not in G 1 and thus the second condition of Definition 5.9 is not met.
Motivated by the HUB-rule, Chikhi at al. [3] introduced the HUB-number of a bipartite graph G. An upper bound for the readability by means of the HUB-number is captured by the next theorem: Theorem 5.13 (Chikhi at al. [3]). Let G be a bipartite graph. Then r(G) ≤ 2 hub(G) −1.
We now present lemma which will show that the upper bound given in Theorem 5.13 is at most equal to the upper bound r(G) ≤ 2 ∆(G)+1 − 1 from [1]. can be decomposed into ∆(G) matchings, which, by the above arguments, gives the decomposition of size at most ∆(G) that satisfies the HUB-rule.
Clearly, combining Theorem 5.13 and Lemma 5.14 we can see that the upper bound 2 ∆(G)+1 − 1 is improved. As an example, consider complete bipartite graph K n,n with n vertices on both sides. The upper bound for the readability of K n,n given by [1] is equal to 2 n+1 − 1 while the upper bound given by Theorem 5.13 is equal to 1, since hub(K n,n ) = 1 achieved by the decomposition mapping each edge to 1. However, the complexity of calculating the HUB-number is not known in general, which limits the use of corresponding bounds either just in theory or for some special graph classes.

Readability of two-dimensional grid graphs
In this chapter we will explore the readability of two-dimensional grid graphs. We will show that readability is at most 3 and moreover, we present a polynomial time algorithm for constructing an optimal overlap labeling of such graphs. Sometimes we will write just grid or grid graph when referring to the two-dimensional grid graph.  Observe that a grid graph of an arbitrary size is bipartite. An example of a grid graph is given in Figure 8.

A polynomial time algorithm for constructing
an optimal overlap labeling of grids Theorem 6.3. Consider two integers m ≥ 3 and n ≥ 3 and let G be the grid graph of size m × n. Then r(G) = 3.
In order to be able to prove the above theorem, we introduce the following lemma:  The idea of the proof of Theorem 6.3 is to show that the lower bound on the readability of a grid graph is 3 and then find an overlap labeling of length 3. In order to prove the lower bound using Theorem 6.4 we will introduce the following graph (already mentioned in the previous chapter): Definition 6.5. The domino is the grid graph of size 2 × 3.
Consider the graph F obtained by taking the graph F = K 1 + domino and adding an edge between K 1 and one of the vertices of the domino with degree 3. Graph F is also bipartite, see Figure 9.
Lemma 6.6. The readability of F is 3.
Proof. We will prove the lemma by contradiction. We use the same denotation of vertices as in Figure 9. Suppose that there exists an overlap labeling of F with len( ) ≤ 2. We may assume without loss of generality that all strings assigned to the vertices of F are of length 2 and moreover, we assume that (1)   Apply similar arguments as above to obtain (2) = ca for some character c = b.
The first character of 5 can not be equal to a since we would have ov(3, 5) > 0.
Since 2 and 5 are adjacent it must hold that (5) = ca. But then, there is no overlapping of length at most 2 between vertices 1 and 5 (recall that we supposed a = b), a contradiction. is not allowed. Thus, there is no overlap between 1 and 7 of length at most 2, a contradiction.
By the above analysis, we conclude that r(F ) ≥ 3. An overlap labeling of length 3 is given in Figure 7 (first image). Thus, r(F ) = 3 as claimed.
Recall that the grid graph of size m × n is defined as the Cartesian product of the paths P m and P n . If we denote the vertices of P m with Z m = {0, 1, . . . m − 1} and the vertices of P n with Z n = {0, 1, . . . , n − 1} then V (G m,n ) = Z m × Z n and two vertices (i, j) and (i , j ) are adjacent if and only if |i − i | + |j − j | = 1. We can thus represent G m,n in the two-dimensional coordinate system as in Figure 8.
For a grid graph G, we will denote by L G function assigning coordinate pairs to vertices of G. Sometimes we will write just (i, j) thinking of vertex u = L −1 G ((i, j)). We now introduce the class of toroidal grid graphs. For positive integers m ≥ 3 and n ≥ 3, the toroidal grid graph T G m,n is the Cartesian product of the cycles C m and C n .
When both m and n are even, T G m,n is bipartite. For the purpose of establishing an upper bound on the readability of grid graphs, we will consider the following special case of toroidal grid graphs. For a positive integer n, we introduce the graph T G n by setting T G n = T G 4n,4n . Lemma 6.7. For every positive integer n, the graph T G n is bipartite and r(T G n ) ≥ 3.
Proof. Since any grid graph is bipartite it is enough to show that vertices denoted with (0, j) and (4n − 1, j) (as well as (j, 0) and (j, 4n − 1) for j = 0, 1, . . . , 4n − 1) are in different parts of bipartition of the grid graph G 4n,4n because vertices denoted with (0, j) and (4n − 1, j) ((j, 0) and (j, 4n − 1)) are not adjacent in G 4n,4n . This is true, since the distance between these two vertices in graph G 4n,4n is 4n − 1, an odd number (recall that two vertices of a connected bipartite graph belong to the same part of the bipartition if and only if the distance between them is an even number). Thus, adding an edge between (0, j) and (4n − 1, j) will not affect bipartiteness. We can use symmetry to infer the same for vertices (j, 0) and (j, 4n − 1) for j ∈ {0, . . . , 4n − 1}.
Obviously, the subgraph of T G n induced by these vertices is isomorphic to F . By Lemma 6.4 and Lemma 6.6 we conclude r(T G n ) ≥ 3.
A bipartition of T G n = (S ∪ T, E) can be obtained by the following rule: In what follows, we will consider this bipartition of T G n . For the sake of simplicity we add 4n vertices (and corresponding edges) to the graph T G n with coordinates (4n, 0), (4n, 1), . . . , (4n, 4n − 1), which we identify with (0, 0), (0, 1), . . . , (0, 4n − 1), respectively, and we also add another 4n vertices with coordinates (0, 4n), (1, 4n), . . . , (4n − 1, 4n), which we identify with (0, 0), (1, 0), . . . , (4n − 1, 4n), respectively. We also add vertex (4n, 4n), which we identify with (0, 0). For example, vertices (4n − 1, 0) and (4n, 0) are adjacent in T G n since (0, 0) and (4n − 1, 0) are adjacent. Note that this identification is natural in view of the fact that the vertex set of T G n is Z 4n × Z 4n . Figure 10  We will now prove that graph T G n is of readability exactly 3. We will define the length of the overlapping for each edge and then construct an overlap labeling. The pseudocode of the algorithm for determining the length of an overlapping of any two adjacent vertices of T G n is given in Algorithm 2. In the algorithm, calculations are done modulo 4n. The result of Algorithm 2 for graph T G 2 is given in Figure 13.
The structure of graphs G 1 , G 2 and G 3 , obtained by Algorithm 2 with the input (T G n , L = L T Gn ) for an arbitrary positive integer n, are captured by Theorem 6.9. Definition 6.8. A regular graph is a graph where each vertex has the same number of neighbors, i.e., every vertex has the same degree. A k-regular graph is a regular graph with vertices of degree k. A k-factor of a graph is spanning k-regular subgraph. Theorem 6.9. Let T G n and function L T Gn be given. Denote by G 1 , G 2 , G 3 the graphs obtained by the Algorithm 2 for the input (T G n , L = L T Gn ). Then G 1 is a 2-factor of (0, 0)  if (i ≡ 0 (mod 2) and j ≡ 0 (mod 4)) or 5 (i ≡ 1 (mod 2) and j ≡ 2 (mod 4)) then 6 u 1 = (i, j); u 2 = (i + 1, j + 1); v 1 = (i, j + 1); v 2 = (i + 1, j); if (i ≡ 2 (mod 4) and j ≡ 0 (mod 2)) or 12 i ≡ 0 (mod 4) and j ≡ 1 (mod 2)) then 13 u 1 = (i, j); v 1 = (i, j + 1); u 2 = (i + 1, j); v 2 = (i + 1, j + 1); T G n consisting of a disjoint union of 4-cycles, while G 2 and G 3 are 1-factors of T G n .
Moreover, every edge of T G n is contained in a unique graph among G 1 , G 2 , G 3 .
Proof. To each added 4-cycle C in step 7, we can associate a unique vertex, denoted by v(C), namely the vertex in C closest to the origin (the vertex u 1 in line 6 of the Algorithm 2). Denote by (i, j) coordinates of v(C).
It follows that any two 4-cycles C and D added in line 7 are vertex-disjoint.
We will now prove that G 2 is a 1-factor of T G n . The edges of G 2 are defined at step 10. Suppose there are vertices u, v, v 1 ∈ V (G 2 ) such that uv ∈ E(G 2 ) and uv 1 ∈ E(G 2 ).
Let L T Gn (u) = (i, j). Since the edges of G 2 are of the form (i, j)(i + 1, j) for some i, j ∈ {0, . . . , 4n−1}, we have two possibilities for the coordinates of v 1 and v 2 . They are . We may assume without loss of generality that L T Gn (v 1 ) = (i − 1, j) and L T Gn (v 2 ) = (i + 1, j). Then, since uv 1 ∈ E(G 2 ) it must hold that i ≡ 1 (mod 2) and since uv 2 ∈ E(G 2 ) we conclude i ≡ 1 (mod 2), a contradiction.
The fact that the graphs G 1 , G 2 and G 3 decompose T G n follows from the tables (Table 1 and Table 2) considering all possible types of edges in T G n . Table 1: Decomposition of the edges of T G n of the type (i, j)(i, j + 1). Each entry is one of the graphs G 1 , G 2 or G 3 , the one containing the edge (i, j)(i, j + 1).
Consider again the graph T G n for an arbitrary positive integer n and denote by S and T the two parts of the bipartition of T G n . Let G 1 , G 2 , G 3 be the graphs obtained by Algorithm 2 for the input (T G n , L T Gn ). To construct an overlap labeling of T G n , we first assign a string of length 3 consisting of null characters to each vertex v ∈ V (T G n ) and then we do the following: Table 2: Decomposition of the edges of T G n of the type (i, j)(i + 1, j). Each entry is one of the graphs G 1 , G 2 or G 3 , the one containing the edge (i, j)(i + 1, j).
then place the character to the third position of the string assigned to v, otherwise (when v ∈ T ) place the character to the first position of the string assigned to v.
2. For each edge of G 2 construct an overlap of length 2.
3. For each edge of G 3 construct an overlap of length 3.
We will now give arguments showing that the above procedure is well defined (see also example in Section 6.2). Denote by s u the string assigned to vertex u and the ith character for i ∈ {1, 2, 3} by s u (i). The first step is obviously well defined since by above G 1 is a disjoint union of 4-cycles. After the first step, each vertex of T G n will be labeled with a character.
Let e = uv ∈ E(G 2 ) and assume without loss of generality that u ∈ S and v ∈ T .
After the first step s u (3) = a and s v (1) = b for some distinct characters a and b (since by the construction of the algorithm, if uv ∈ E(G 2 ) then it can not happen that uv ∈ E(G 1 )). To make an overlap of length 2 we set s u (2) = b and s v (2) = a.
The third step is the most difficult one. After the second step, for each u ∈ V (T G n ) the string s u has exactly two characters different from the null character (since G 2 is a 1-factor of T G n ). We will show that if there is an edge e = uv ∈ E(G 3 ) and both s u and s v have two characters different from the null character (i.e., s u (i) = * for i ∈ {2, 3} and s v (j) = * for j ∈ {1, 2}), then s u (2) = s v (2). Let uv ∈ E(G 3 ) and u ∈ S, v ∈ T . By above, there exists e 1 ∈ E(G 2 ) such that u is an endpoint of e 1 and there exists e 2 ∈ E(G 2 ) such that v is an endpoint of e 2 . In that case let u 1 be vertex of V (T G n ) such that uu 1 ∈ E(G 2 ) and v 1 ∈ V (T G n ) such that vv 1 ∈ E(G 2 ).
By the above arguments, we have an assignment to vertices of T G n such that if e = uv ∈ E(T G n ) we have ov(s u , s v ) > 0. To prove that such assignment is an overlap labeling of T G n we need to prove that if for some distinct vertices u ∈ S, v ∈ T we have ov(s u , s v ) > 0 then uv ∈ E(T G n ). We will analyze only one case since we can use symmetry to state the same arguments for the other cases.
Suppose that for some u ∈ S and v ∈ T , ov(s u , s v ) > 0. If ov(s u , s v ) = 1 then we may assume that vertices which belong to the same 4-cycle in G 1 as vertex u are denoted with (i − 1, j), (i, j + 1), (i − 1, j + 1), the other cases will follow by symmetry (see Figure 11). Also, since uu 1 ∈ E(G 2 ) by the construction of graph T G n and above assumptions it must follow that LG T Gn (u 1 ) = (i + 1, j).  (1)). But, by the construction of the graph T G n , vertices (i, j) and (i + 3, j) are not adjacent (since a = c) , which means that L T Gn (v 1 ) can not be equal to (i + 2, j) (see Figure 11, right image).
Lastly if L T Gn (v 1 ) = (i + 1, j − 1) then by the algorithm (since vv 1 ∈ E(G 2 )) the only possibility is that L T Gn (v) = (i, j − 1). But then, by the construction of the graph T G n u and v are adjacent and we obtained desired (see Figure 12).
There are three further cases with respect to the position of u in the 4-cycle of G 1 .
In all those cases we apply similar arguments to the ones given above.
By the stated arguments, the assignment obtained by above procedure is an overlap a a a a c c c Figure 11: The left image corresponds to the case v 1 = L −1 T Gn (i + 2, j − 1). The right image corresponds to the case v = L −1 T Gn (i, j + 3). Figure 12: The third case of above proof: if v 1 = (i + 1, j − 1) and vv 1 ∈ E(G 2 ) then the only possibility is v = (i, j − 1). In that case uv ∈ E(T G n ). labeling of length 3. Combining this result with Lemma 6.7 we get that r(T G n ) = 3. Now we are able to prove Theorem 6.3: Proof of Theorem 6.3. Let G m,n be grid graph of size m × n, m ≥ 3 and n ≥ 3. One can easily check that the subgraph of G m,n induced by vertices (0, 1), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2,2) is isomorphic to graph F . By Theorem 6.4 and Lemma 6.6 we obtain r(G m,n ) ≥ 3. Let k = max{m, n} + 1. Clearly, G m,n is induced subgraph of T G k and hence r(G m,n ) ≤ r(T G k ). By the above discussion, r(T G k ) = 3. Thus

An example
We conclude the chapter with a concrete example illustrating the construction of an overlap labeling of a toroidal grid graph T G 2 as described above (see Figure 13).
Let G 1 , G 2 and G 3 be the graphs obtained by Algorithm 2 for input (T G 2 , L = L T G 2 ). G 1 is a disjoint union of 4-cycles denoted by red color, G 2 consists of edges colored with blue color and G 3 consists of edges colored with green color. By the procedure for constructing an optimal overlap labeling, we first assign a unique character to each 4-cycle (note that the size of the alphabet used to construct an overlap labeling of length 3 is equal to number of 4-cycles in G 1 ). Suppose for example that we assign characters a, b, c to cycles with lower left vertices (0, 0), (2, 1), (2, 7), respectively. Since (1, 1)(2, 1) ∈ E(G 2 ) and (1, 0)(2, 0) ∈ E(G 2 ) we assign strings * ba, ba * , * ac to vertices (1, 1), (2, 1), (2, 0), respectively (recall that * stands for null character, i.e., we did not yet assign any character on the position where * is placed). Since (2, 0)(2, 1) ∈ E(G 3 ) we have to construct overlapping of length 3. This is possible since the second character of (2, 1) is equal to the second character of (2, 0). We assign string bac to both vertices (2, 0) and (2, 1) and make overlapping of length 3 without affecting to overlaps constructed while processing edges of G 2 . The other edges are processed similarly.

Conclusion
In the final project paper, we reviewed an algorithm for building a set of strings given its overlap graph given by Braga and Meidanis [1]. Although the derived running time of the algorithm is exponential in the maximum degree, one can make it polynomial using programming languages which allows memory manipulation (e.g., using pointers) such as C++. However, the upper bound for the readability derived with Algorithm 1 is in general very weak. This motivated us to formulate an ILP model for the exact computation of readability (for balanced bipartite graphs as well as for digraphs).While polynomial, the number of variables and constraints of the ILPs can be large already for moderately sized graphs. However, with fast ILP solvers, the models can be used to understand the behavior of readability of small graphs and to state hypotheses for readability in general. We implemented the ILP for bipartite graphs in Java [6] using IBM R ILOG R CPLEX R Optimization Studio [5]. The implementation is available at [7].
We reviewed bounds for readability using tools from graph theory developed in [3] and presented theorems that are the basis for the derivation of polynomial time algorithms for checking if a graph is of readability at most 2. The lower bound given by the parameter distinctness can be computed in polynomial time. The time complexity of computing bounds given by HUB -number of a graph is unknown and such bounds can therefore only be used in theory. However, this theory motivated us to establish the readability of grid graphs and toroidal grid graphs. We showed that readability of such graphs is at most 3 and moreover for any (toroidal) grid graph of size m × n for some integers m ≥ 3, n ≥ 3, the readability is exactly 3. We also presented a polynomial time algorithm for constructing an optimal overlap labeling of such graphs. It can be verified that the HUB-number of graph F (see Figure 9) is at least 3, which implies that for all large enough grid graphs and for all toroidal grid graphs, the readability coincides with their HUB-number (which in general is only a lower bound for the readability).