Conditions for bipartite graph to be planar with no edges going around the vertices
-
04-11-2019 - |
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:
- All vertices of one part are drawn on a single vertical line. Vertices of the other part are drawn on a parallel verticle line.
- Edges do not intersect except at vertices.
- 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.
The top two graphs are the only obstructions I could find. My questions are:
- Does this problem have a name?
- Any other obstructions that I missed?
- 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