Search

The following Ramsey-type question is one of the central problems in combinatorial geometry. Given a collection of certain geometric objects in the plane (e.g. segments, rectangles, convex sets, arcwise connected sets) of size n, what is the size of the largest subcollection in which either any two elements have a nonempty intersection, or any two elements are disjoint? We prove that there exists an absolute constant c>0 such that if C is a collection of n curves in the plane, then C contains at least nc elements that are pairwise intersecting, or n c elements that are pairwise disjoint. This resolves a problem raised by Alon, Pach, Pinchasi, Radoičić and Sharir, and Fox and Pach. Furthermore, as any geometric object can be arbitrarily closely approximated by a curve, this shows that the answer to the aforementioned question is at least nc for any collection of n geometric objects. [ABSTRACT FROM AUTHOR]

Let C and D be hereditary graph classes. Consider the following problem: given a graph G ∈ D , find a largest, in terms of the number of vertices, induced subgraph of G that belongs to C . We prove that it can be solved in 2 o (n) time, where n is the number of vertices of G, if the following conditions are satisfied: the graphs in C are sparse, i.e., they have linearly many edges in terms of the number of vertices; the graphs in D admit balanced separators of size governed by their density, e.g., O (Δ) or O (m) , where Δ and m denote the maximum degree and the number of edges, respectively; and the considered problem admits a single-exponential fixed-parameter algorithm when parameterized by the treewidth of the input graph. This leads, for example, to the following corollaries for specific classes C and D : a largest induced forest in a P t -free graph can be found in 2 O ~ (n 2 / 3) time, for every fixed t; and a largest induced planar graph in a string graph can be found in 2 O ~ (n 2 / 3) time. [ABSTRACT FROM AUTHOR]

Conflict-free coloring (in short, CF-coloring) of a graph G = (V , E) is a coloring of V such that the punctured neighborhood of each vertex contains a vertex whose color differs from the color of any other vertex in that neighborhood. Bounds on CF-chromatic numbers have been studied both for general graphs and for intersection graphs of geometric shapes. In this paper we obtain such bounds for several classes of string graphs, i.e., intersection graphs of curves in the plane: (i) we provide a general upper bound of O (χ (G) 2 log n) on the CF-chromatic number of any string graph G with n vertices in terms of the classical chromatic number χ (G) . This result stands in contrast to general graphs where the CF-chromatic number can be Ω (n) already for bipartite graphs. (ii) For some central classes of string graphs, the CF-chromatic number is as large as Θ (n) , which was shown to be the upper bound for any graph even in the non-geometric context. For several such classes (e.g., intersection graphs of frames) we prove a tight bound of Θ (log n) with respect to the relaxed notion of k-CF-coloring (in which the punctured neighborhood of each vertex contains a color that appears at most k times), for a small constant k. (iii) We obtain a general upper bound on the k-CF chromatic number of arbitrary hypergraphs (i.e., the number of colors needed to color the vertices, such that in each hyperedge there is a color that appears at most k times): any hypergraph with m hyperedges can be k-CF colored with O ~ (m 1 k + 1 ) colors. This bound, which extends a bound of Pach and Tardos (Comb Probab Comput 18(5):819–834, 2009), is tight for some string graphs, up to a logarithmic factor. (iv) Our fourth result concerns circle graphs in which coloring problems are motivated by VLSI designs. We prove a tight bound of Θ (log n) on the CF-chromatic number of circle graphs, and an upper bound of O (log 3 n) for a wider class of string graphs that contains circle graphs, namely, intersection graphs of grounded L-shapes. [ABSTRACT FROM AUTHOR]

A string graph is the intersection graph of a family of continuous arcs in the plane. The intersection graph of a family of plane convex sets is a string graph, but not all string graphs can be obtained in this way. We prove the following structure theorem conjectured by Janson and Uzzell: The vertex set of almost all string graphs on n vertices can be partitioned into five cliques such that some pair of them is not connected by any edge ( n → ∞ ). We also show that every graph with the above property is an intersection graph of plane convex sets. As a corollary, we obtain that almost all string graphs on n vertices are intersection graphs of plane convex sets. [ABSTRACT FROM AUTHOR]

We consider subexponential algorithms finding weighted homomorphisms from intersection graphs of curves (string graphs) with n vertices to a fixed graph H. We provide a complete dichotomy: if H has no two vertices sharing two common neighbors, then the problem can be solved in time 2 O (n 2 / 3 log ⁡ n) , otherwise there is no subexponential algorithm, assuming the ETH. Then we consider locally constrained homomorphisms. We show that for each target graph H , the locally injective and locally bijective homomorphism problems can be solved in time 2 O (n log ⁡ n) in string graphs. For locally surjective homomorphisms we show a dichotomy for H being a path or a cycle. If H is P 3 or C 4 , then the problem can be solved in time 2 O (n 2 / 3 log 3 / 2 ⁡ n) in string graphs; otherwise, assuming the ETH, there is no subexponential algorithm. As corollaries, we obtain new results concerning the complexity of homomorphism problems in P t -free graphs. [ABSTRACT FROM AUTHOR]

Background: De novo genome assembly relies on two kinds of graphs: de Bruijn graphs and overlap graphs. Overlap graphs are the basis for the Celera assembler, while de Bruijn graphs have become the dominant technical device in the last decade. Those two kinds of graphs are collectively called assembly graphs. Results: In this review, we discuss the most recent advances in the problem of constructing, representing and navigating assembly graphs, focusing on very large datasets. We will also explore some computational techniques, such as the Bloom filter, to compactly store graphs while keeping all functionalities intact. Conclusions: We complete our analysis with a discussion on the algorithmic issues of assembling from long reads (e.g., PacBio and Oxford Nanopore). Finally, we present some of the most relevant open problems in this field. [ABSTRACT FROM AUTHOR]

An outerstring graph is an intersection graph of curves that lie in a common half-plane and have one endpoint on the boundary of that half-plane. We prove that the class of outerstring graphs is X-bounded, which means that their chromatic number is bounded by a function of their clique number. This generalizes a series of previous results on X-boundedness of outerstring graphs with various additional restrictions on the shape of curves or the number of times the pairs of curves can cross. The assumption that each curve has an endpoint on the boundary of the half-plane is justified by the known fact that triangle-free intersection graphs of straight-line segments can have arbitrarily large chromatic number. [ABSTRACT FROM AUTHOR]

A path is a simple, piecewise linear curve made up of alternating horizontal and vertical line segments in the plane. A k-bend path is a path made up of at most k + 1 line segments. A Bk-VPG representation of a graph is a collection of k-bend paths such that each path in the collection represents a vertex of the graph and two such paths intersect if and only if the vertices they represent are adjacent in the graph. The graphs that have a Bk-VPG representation are calledBk-VPG graphs. The bend number of a graph G, denoted by bend(G), is the minimum integer k for which G has a Bk-VPG representation. In this paper, we study the relationship between poset dimension and bend number of cocomparability graphs. It is known that the poset dimension dim(G) of a cocomparability graph G is greater than or equal to its bend number bend(G). Cohen et al. (order2016) asked for examples of cocomparability graphs with low bend number and high poset dimension. We answer this question by proving that for each m , t ∈ ℕ , there exists a cocomparability graph Gt, m with t < bend(Gt, m) ≤ 4t + 29 and dim(Gt, m) − bend(Gt, m) > m. The techniques used to prove the above result allow us to partially address the open question posed by Chaplick et al. (wg2012) who asked whether Bk-VPG-chordal ⫋ B k + 1 -VPG-chordal for all k ∈ ℕ . We address this by proving that there are infinitely many m ∈ ℕ such that Bm-VPG-split ⫋ B m + 1 -VPG-split which provides infinitely many positive examples. We use the same techniques to prove that, for all t ∈ ℕ , Bt-VPG- Forb (C ≥ 5) ⫋ B 4 t + 29 -VPG-Forb(C≥ 5), where Forb(C≥ 5) denotes the family of graphs that does not contain induced cycles of length greater than 4. Furthermore, we show that for all t ∈ ℕ , PBt-VPG-split ⫋ P B 36 t + 80 -VPG-split, where PBt-VPG denotes the class of graphs with proper bend number at most t (i.e. it has a Bt-VPG representation in which two paths have only finitely many intersection points, each intersection point belongs to exactly two paths, and whenever two paths intersect they cross each other). [ABSTRACT FROM AUTHOR]

Planar graphs are known to allow subexponential algorithms running in time 2 O (n) or 2 O (n log n) for most of the paradigmatic problems, while the brute-force time 2 Θ (n) is very likely to be asymptotically best on general graphs. Intrigued by an algorithm packing curves in 2 O (n 2 / 3 log n) by Fox and Pach (SODA'11), we investigate which problems have subexponential algorithms on the intersection graphs of curves (string graphs) or segments (segment intersection graphs) and which problems have no such algorithms under the Exponential Time Hypothesis (ETH). Among our results, we show that, quite surprisingly, 3-Coloring can also be solved in time 2 O (n 2 / 3 log O (1) n) on string graphs while an algorithm running in time 2 o (n) for 4-Coloring even on axis-parallel segments (of unbounded length) would disprove the ETH. For 4-Coloring of unit segments, we show a weaker lower bound, excluding a 2 o (n 2 / 3) algorithm (under the ETH). The construction exploits the celebrated Erdős–Szekeres theorem. The subexponential running time also carries over to Min Feedback Vertex Set, but not to Min Dominating Set and Min Independent Dominating Set. [ABSTRACT FROM AUTHOR]

We prove that for every integer t ⩾ 1 , the class of intersection graphs of curves in the plane each of which crosses a fixed curve in at least one and at most t points is χ -bounded. This is essentially the strongest χ -boundedness result one can get for those kind of graph classes. As a corollary, we prove that for any fixed integers k ⩾ 2 and t ⩾ 1 , every k-quasi-planar topological graph on n vertices with any two edges crossing at most t times has O (n log n) edges. [ABSTRACT FROM AUTHOR]

Some recent results (Bauer et al. in Algorithms in bioinformatics, Springer, Berlin, pp 326-337, 2012; Cox et al. in Algorithms in bioinformatics, Springer, Berlin, pp. 214-224, 2012; Rosone and Sciortino in The nature of computation. Logic, algorithms, applications, Springer, Berlin, pp 353-364, 2013) have introduced external-memory algorithms to compute self-indexes of a set of strings, mainly via computing the Burrows-Wheeler transform of the input strings. The motivations for those results stem from Bioinformatics, where a large number of short strings (called reads) are routinely produced and analyzed. In that field, a fundamental problem is to assemble a genome from a large set of much shorter samples extracted from the unknown genome. The approaches that are currently used to tackle this problem are memory-intensive. This fact does not bode well with the ongoing increase in the availability of genomic data. A data structure that is used in genome assembly is the string graph, where vertices correspond to samples and arcs represent two overlapping samples. In this paper we address an open problem of Simpson and Durbin (Bioinformatics 26(12):i367-i373, 2010): to design an external-memory algorithm to compute the string graph. [ABSTRACT FROM AUTHOR]

We analyse properties to show the strict containment between some natural classes of geometric intersection graphs. For example, we show that, for each integer k ≥ 1 , the class of intersection graphs of segments with k different lengths is a strict subclass of the class of intersection graphs of segments with k + 1 different lengths, and the class of outer-segment graphs is a strict subclass of the class of outer-string graphs. [ABSTRACT FROM AUTHOR]

The large amount of short read data that has to be assembled in future applications, such as in metagenomics or cancer genomics, strongly motivates the investigation of disk-based approaches to index next-generation sequencing (NGS) data. Positive results in this direction stimulate the investigation of efficient external memory algorithms for de novo assembly from NGS data. Our article is also motivated by the open problem of designing a space-efficient algorithm to compute a string graph using an indexing procedure based on the Burrows-Wheeler transform (BWT). We have developed a disk-based algorithm for computing string graphs in external memory: the light string graph (LSG). LSG relies on a new representation of the FM-index that is exploited to use an amount of main memory requirement that is independent from the size of the data set. Moreover, we have developed a pipeline for genome assembly from NGS data that integrates LSG with the assembly step of SGA (Simpson and Durbin, ), a state-of-the-art string graph-based assembler, and uses BEETL for indexing the input data. LSG is open source software and is available online. We have analyzed our implementation on a 875-million read whole-genome dataset, on which LSG has built the string graph using only 1GB of main memory (reducing the memory occupation by a factor of 50 with respect to SGA), while requiring slightly more than twice the time than SGA. The analysis of the entire pipeline shows an important decrease in memory usage, while managing to have only a moderate increase in the running time. [ABSTRACT FROM AUTHOR]

We show that three subclasses of bounded treewidth graphs are well quasi ordered by refinements of the minor order. Specifically, we prove that graphs with bounded vertex cover are well quasi ordered by the induced subgraph order, graphs with bounded feedback vertex set are well quasi ordered by the topological-minor order, and graphs with bounded circumference are well quasi ordered by the induced minor order. Our results give algorithms for recognizing any graph family in these classes which is closed under the corresponding minor order refinement. [ABSTRACT FROM AUTHOR]

Abstract: We investigate the class of vertex intersection graphs of paths on a grid, and specifically consider the subclasses that are obtained when each path in the representation has at most k bends (turns). We call such a subclass the -VPG graphs, . We present a complete hierarchy of VPG graphs relating them to other known families of graphs. String graphs are equivalent to VPG graphs. The grid intersection graphs [S. Bellantoni, I. Ben-Arroyo Hartman, T. Przytycka, S. Whitesides, Grid intersection graphs and boxicity, Discrete Math. 114, (1993), 41–49; I. Ben-Arroyo Hartman, I. Newman, R. Ziv, On grid intersection graphs, Discrete Math. 87(1), (1991), 41–52] are shown to be equivalent to the bipartite -VPG graphs. Chordal -VPG graphs are shown to be exactly Strongly Chordal -VPG graphs. We prove the strict containment of -VPG and circle graphs into -VPG. Planar graphs are known to be in the class of string graphs, and we prove here that planar graphs are -VPG graphs. In the case of -VPG graphs, we observe that a set of horizontal and vertical segments have strong Helly number 2. We show that the coloring problem for -VPG graphs, for , is NP-complete and give a 2-approximation algorithm for coloring -VPG graphs. Furthermore, we prove that triangle-free -VPG graphs are 4-colorable, and this is best possible. [Copyright &y& Elsevier]

There are three general lower bound techniques for the crossing numbers of graphs: the Crossing Lemma, the bisection method and the embedding method. In this contribution, we present their adaptations to the minor crossing number. Using the adapted bounds, we improve on the known bounds on the minor crossing number of hypercubes. We also point out relations of the minor crossing number to string graphs and establish a lower bound for the standard crossing number in terms of Randič index. [ABSTRACT FROM AUTHOR]

Abstract: We show that for every n there are two simple curves on the torus intersecting at least n times without the two curves folding or spiralling with respect to each other. [Copyright &y& Elsevier]

A string graph is the intersection graph of a set of curves in the plane. Each curve is represented by a vertex, and an edge between two vertices means that the corresponding curves intersect. We show that string graphs can be recognized in NP. The recognition problem was not known to be decidable until very recently, when two independent papers established exponential upper bounds on the number of intersections needed to realize a string graph (Mutzel (Ed.), Graph Drawing 2001, Lecture Notes in Computer Science, Springer, Berlin; Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC-2001)). These results implied that the recognition problem lies in NEXP. In the present paper we improve this by showing that the recognition problem for string graphs is in NP, and therefore NP-complete, since Kratochvı´l showed that the recognition problem is NP-hard (J. Combin Theory, Ser. B 52). The result has consequences for the computational complexity of problems in graph drawing, and topological inference. We also show that the string graph problem is decidable for surfaces of arbitrary genus. [Copyright &y& Elsevier]

Microbial organisms have diverse populations, where using a single linear reference sequence in comparative studies introduces reference-bias in downstream analyses, and leads to a failure to account for variability in the population. Recently, pan-genome graphs have emerged as an alternative to the traditional linear reference with many successful applications and a rapid increase in the number of methods available in the literature. Despite this enthusiasm, there has been no attempt at exploring these graph construction methods in depth, demonstrating their practical use. In this study, we aim to develop a general guide to help researchers who may want to incorporate pan-genomes in their analyses of microbial organisms. We evaluated the state-of-the art pan-genome construction tools to model a collection of 70 Acinetobacter baumannii strains. Our results suggest that all tools produced pan-genome graphs conforming to our expectations based on previous literature, and that their approach to homologue detection is likely to be the most influential in determining the final size and complexity of the pan-genome. The graphs overlapped most in the core pan-genome content while the cloud genes varied significantly among tools. We propose an alternative approach for pan-genome construction by combining two of the tools, Panaroo and Ptolemy, to further exploit them in downstream analyses, and demonstrate the effectiveness of our pipeline for structural variant calling in beta-lactam resistance genes in the same set of A. baumannii isolates, identifying various transposon structures for carbapenem resistance in chromosome, as well as plasmids. We identify a novel plasmid structure in two multidrug-resistant clinical isolates that had previously been studied, and which could be important for their resistance phenotypes.