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

Alecu, BogdanLozin, VadimZamaraev, Viktorde Werra, Dominique2018-12-132018-12-132018-12-132018-01-0110.1007/978-3-319-78825-8_16https://infoscience.epfl.ch/handle/20.500.14299/152238WOS:000445803300016In 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.Computer Science, Theory & MethodsComputer Scienceinduced subgraphsLetter Graphs and Geometric Grid Classes of Permutations: Characterization and Recognitiontext::conference output::conference proceedings::conference paper