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



To see that these conditions are equivalent, observe first that (1) implies (2), which implies (3). And if there are no three nested pairs in the notation, then G can be drawn planarly by the following very simple algorithm: construct G by adding vertices one or two at a time as indicated by the notation. Draw each red vertex on the x axis, and each blue vertex on the y axis. Within a single color class, draw the vertices on alternating sides of the origin, with each new vertex farther from the origin than the previously drawn vertex on the same side; that is, draw the red vertices with x coordinates 1, -1, 2, -2, etc, and similarly for the blue vertices. When each vertex is added, draw edges connecting it to one or two of the outermost vertices of the other color (depending on whether it is within one or two levels of nesting); these edges are outside the convex hull of all the other vertices, so they cannot cross anything.

The image above was generated by an implementation of the algorithm. You may be wondering why there are more blue vertices below the horizontal axis than above it; it's because the original output was in SVG format and in that format the origin is at the top left and increasing coordinate values go downwards. So the first blue vertex generated by the algorithm is the one just below the horizontal axis, and the last one is the bottommost.
Tags: chord diagrams, graph drawing, graph theory
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments