If G is a bipartite permutation graph, then the following conditions are equivalent: (1) G is planar, (2) G contains no K3,3 subgraph, and (3) in the notation from my previous post for G, the pairs of "><" characters are never nested more than two levels deep.
Here's an example, for the graph denoted by the string ">>\\/\//\</\><//\>\\</<".
Some changes have been made to LiveJournal, and we hope you enjoy them! As we continue to improve the site on a daily basis to make your experience here better and faster, we would greatly appreciate your feedback about these changes. Please let us know what we can do for you!