TY - GEN
T1 - Bipartite graphs of small readability
AU - Chikhi, Rayan
AU - Jovičić, Vladan
AU - Kratsch, Stefan
AU - Medvedev, Paul
AU - Milanič, Martin
AU - Raskhodnikova, Sofya
AU - Varma, Nithin
N1 - Funding Information:
Acknowledgments. The result of Sect. 3.1 was discovered with the help of The On-Line Encyclopedia of Integer Sequences ©R [22]. This work has been supported in part by NSF awards DBI-1356529, CCF-1439057, IIS-1453527, and IIS-1421908 to P.M. and by the Slovenian Research Agency (I0-0035, research program P1-0285 and research projects N1-0032, J1-6720, and J1-7051) to M.M. The authors S.R. and N.V. were supported by NSF grant CCF-1422975 to S.R. The author N.V. was also supported by Pennsylvania State University College of Engineering Fellowship, PSU Graduate Fellowship, and by NSF grant IIS-1453527 to P.M. The main idea of the proof of Lemma 4 was developed by V.J. in his undergraduate final project paper [13] at the University of Primorska.
Publisher Copyright:
© 2018, Springer International Publishing AG, part of Springer Nature.
PY - 2018
Y1 - 2018
N2 - We study a parameter of bipartite graphs called readability, introduced by Chikhi et al. (Discrete Applied Mathematics 2016) and motivated by applications of overlap graphs in bioinformatics. The behavior of the parameter is poorly understood. The complexity of computing it is open and it is not known whether the decision version of the problem is in NP. The only known upper bound on the readability of a bipartite graph (Braga and Meidanis, LATIN 2002) is exponential in the maximum degree of the graph. Graphs that arise in bioinformatic applications have low readability. In this paper we focus on graph families with readability o(n), where n is the number of vertices. We show that the readability of n-vertex bipartite chain graphs is between (Formula Presented) and (Formula Presented). We give an efficiently testable characterization of bipartite graphs of readability at most 2 and completely determine the readability of grids, showing in particular that their readability never exceeds 3. As a consequence, we obtain a polynomial-time algorithm to determine the readability of induced subgraphs of grids. One of the highlights of our techniques is the appearance of Euler’s totient function in the proof of the upper bound on the readability of bipartite chain graphs. We also develop a new technique for proving lower bounds on readability, which is applicable to dense graphs with a large number of distinct degrees.
AB - We study a parameter of bipartite graphs called readability, introduced by Chikhi et al. (Discrete Applied Mathematics 2016) and motivated by applications of overlap graphs in bioinformatics. The behavior of the parameter is poorly understood. The complexity of computing it is open and it is not known whether the decision version of the problem is in NP. The only known upper bound on the readability of a bipartite graph (Braga and Meidanis, LATIN 2002) is exponential in the maximum degree of the graph. Graphs that arise in bioinformatic applications have low readability. In this paper we focus on graph families with readability o(n), where n is the number of vertices. We show that the readability of n-vertex bipartite chain graphs is between (Formula Presented) and (Formula Presented). We give an efficiently testable characterization of bipartite graphs of readability at most 2 and completely determine the readability of grids, showing in particular that their readability never exceeds 3. As a consequence, we obtain a polynomial-time algorithm to determine the readability of induced subgraphs of grids. One of the highlights of our techniques is the appearance of Euler’s totient function in the proof of the upper bound on the readability of bipartite chain graphs. We also develop a new technique for proving lower bounds on readability, which is applicable to dense graphs with a large number of distinct degrees.
UR - http://www.scopus.com/inward/record.url?scp=85049680844&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85049680844&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-94776-1_39
DO - 10.1007/978-3-319-94776-1_39
M3 - Conference contribution
AN - SCOPUS:85049680844
SN - 9783319947754
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 467
EP - 479
BT - Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings
A2 - Zhu, Daming
A2 - Wang, Lusheng
PB - Springer Verlag
T2 - 24th International Conference on Computing and Combinatorics Conference, COCOON 2018
Y2 - 2 July 2018 through 4 July 2018
ER -