Letter Graphs and Geometric Grid Classes of Permutations: Characterization and Recognition

摘要

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.