0xDE (11011110 ) wrote,

Planar bipartite permutation graphs

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 ">>\\/\//\</\><//\>\\</<".

Read more...Collapse )
Tags: chord diagrams, graph drawing, graph theory
  • Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded