Fast recognition of Baxter permutations using syntactical and complete bipartite composite dag's

A correspondence is developed between permutations and two-dimensional digraphs. When the graphs are also required to be completely bipartite composite (CBC), their permutations then correspond to a class called the Baxter permutations. A permutation can be tested for the Baxter condition by a linear time processing of its digraph. This processing involves a pair of traversals of the digraph and is made possible by exploiting a relationship with the syntactical graphs used in language theory.