On the readability of overlap digraphs

We introduce the graph parameter readability   and study it as a function of the number of vertices in a graph. Given a digraph DD, an injective overlap labeling assigns a unique string to each vertex such that there is an arc from xx to yy if and only if xx properly overlaps yy. The readability of DD is the minimum string length for which an injective overlap labeling exists. In applications that utilize overlap digraphs (e.g., in bioinformatics), readability reflects the length of the strings from which the overlap digraph is constructed. We study the asymptotic behavior of readability by casting it in purely graph theoretic terms (without any reference to strings). We prove upper and lower bounds on readability for certain graph families and general graphs.