Alecu, BogdanLozin, Vadimde Werra, DominiqueZamaraev, Viktor2020-07-122020-07-122020-07-122020-09-1510.1016/j.dam.2020.01.038https://infoscience.epfl.ch/handle/20.500.14299/170016WOS:000543301700037In this paper, we reveal an intriguing relationship between two seemingly unrelated notions: letter graphs and geometric grid classes of permutations. An important property common for both of them is well-quasi-orderability, implying, in a non-constructive way, a polynomial-time recognition of geometric grid classes of permutations and k-letter graphs for a fixed k. However, explicit algorithms are available only for k = 2. In this paper, we present the first explicit polynomial-time algorithm for the recognition of 3-letter graphs over a cyclic decoder. It is based on a structural characterization of graphs in this class. (C) 2020 Elsevier B.V. All rights reserved.Mathematics, AppliedMathematicsletter graphspermutationsgeometric grid classesinduced subgraphstext::journal::journal article::research article