conference paper
Letter Graphs and Geometric Grid Classes of Permutations: Characterization and Recognition
January 1, 2018
Combinatorial Algorithms, Iwoca 2017
In this paper, we reveal an intriguing relationship between two seemingly unrelated notions: letter graphs and geometric grid classes of permutations. We also present the first constructive polynomial-time algorithm for the recognition of 3-letter graphs.