Question

A bipartite graph is planar iff it has no $K_{3, 3}$ or $K_5$ minors.

I am looking for a necessary or/and sufficient conditions to allow planar drawings with no edges "going around" sets of vertices. These are drawings satisfying:

  1. All vertices of one part are drawn on a single vertical line. Vertices of the other part are drawn on a parallel verticle line.
  2. Edges do not intersect except at vertices.
  3. Edges are all in the infinite strip between the two vertical lines in point 1.

For example, all drawings here except the bottom right are non-examples. The bottom-left graph can be re-drawn to satisfy the conditions by swapping the positions of Q and R. The tops two graphs cannot be redrawn to satisfy the conditions.

enter image description here

The top two graphs are the only obstructions I could find. My questions are:

  1. Does this problem have a name?
  2. Any other obstructions that I missed?
  3. Any hints on how I can prove that these two obstructions (along with anything I missed), as minors of course, are necessary and sufficient.

Note that this is not the same as being outer-planar, $K_{2, 2}$ is outer-planar (can be drawn as a square) but it cannot be drawn to satisfy the conditions I mention above.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top