  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.
