2018/04/27 by Alecu, Bogdan, Lozin, Vadim, de Werra, Dominique +1
#05C75 #05C85 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1804.11217
In 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, constructive algorithms are available only for k=2. In this paper, we present the first constructive polynomial-time algorithm for the recognition of 3-letter graphs. It is based on a structural characterization of graphs in this class.