I'm interested in permutations classes defined by one or several excluded patterns of length 4. In particular, the following classes seem interesting but not so-well studied algorithmically.
the skew-merged permutations consist of the permutations that can be partitioned in an increasing and a decreasing subsequence; their basis is $\{3412, 2143\}$.
the vexillary permutations have basis $\{2143\}$; they have been introduced by Lascoux and Schützenberger in connection with Schubert calculus ('Schubert polynomials and the Littlewood–Richardson rule', Letters in Mathematical Physics 10(2), 111-124).
By the basis definition, it is immediate that a permutation $\pi$ is skew-merged iff both $\pi$ and $\pi^r$ are vexillary; this suggests some possible link between these two classes. I am interested in the following algorithmic questions:
Are there linear-time recognition algorithms for these classes? By the previous remark, an algorithm for class 2 would immediately yield an algorithm for class 1, although I suspect a more direct algorithm to exist in that case.
What is the complexity of the subpattern problem for two skew-merged or two vexillary permutations? The subpattern problem is known to be polynomial for separable and 2-increasing permutations, and these classes seem the next to study.