Abstract Lettericity is a graph parameter responsible for many attractive structural properties. In particular, graphs of bounded lettericity have bounded linear clique-width and they are well-quasi-ordered by induced subgraphs. The latter property implies that any hereditary class of graphs of bounded lettericity can be described by finitely many forbidden induced subgraphs. This, in turn, implies, in a non-constructive way, polynomial-time recognition of such classes. However, no constructive algorithms and no specific bounds on the size of forbidden graphs are available up to date. In the present paper, we develop an algorithm that recognizes n -vertex graphs of lettericity at most k in time $$f(k) \cdot n^3$$ and show that any minimal graph of lettericity more than k has at most $$2^{O(k^2\log k)}$$ vertices.

Abstract. Given two [Formula: see text]-vertex graphs [Formula: see text] and [Formula: see text] of bounded treewidth, is there an [Formula: see text]-vertex graph [Formula: see text] of bounded treewidth having subgraphs isomorphic to [Formula: see text] and [Formula: see text]? Our main result is a negative answer to this question, in a strong sense: we show that the answer is no even if [Formula: see text] is a binary tree and [Formula: see text] is a ternary tree. We also provide an extensive study of cases where such “gluing” is possible. In particular, we prove that if [Formula: see text] has treewidth [Formula: see text] and [Formula: see text] has pathwidth [Formula: see text], then there is an [Formula: see text]-vertex graph of treewidth at most [Formula: see text] containing both [Formula: see text] and [Formula: see text] as subgraphs.

Abstract The class of quasi-chain graphs is an extension of the well-studied class of chain graphs. This latter class enjoys many nice and important properties, such as bounded clique-width, implicit representation, well-quasi-ordering by induced subgraphs, etc. The class of quasi-chain graphs is substantially more complex. In particular, this class is not well-quasi-ordered by induced subgraphs, and the clique-width is not bounded in it. In the present paper, we show that the universe of quasi-chain graphs is at least as complex as the universe of permutations by establishing a bijection between the class of all permutations and a subclass of quasi-chain graphs. This implies, in particular, that the induced subgraph isomorphism problem is NP-complete for quasi-chain graphs. On the other hand, we propose a decomposition theorem for quasi-chain graphs that implies an implicit representation for graphs in this class and efficient solutions for some algorithmic problems that are generally intractable.

We uncover a connection between two seemingly unrelated notions: lettericity, from structural graph theory, and geometric griddability, from the world of permutation patterns. Both of these notions capture important structural properties of their respective classes of objects. We prove that these notions are equivalent in the sense that a permutation class is geometrically griddable if and only if the corresponding class of inversion graphs has bounded lettericity.