Conditions for bipartite graph to be planar with no edges going around the vertices

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.

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.

Answer 1

Your graphs are exactly the graphs of path-width $1$ or, equivalently, the forests each of whose components is a caterpillar. Caterpillars have two relevant characterizations:

• they're the trees in which there is a single path containing every vertex of degree more than $1$;

• they're the trees in which every vertex has at most two non-leaf neighbours.

Lemma 1. Every caterpillar is in your class.

Proof. Let $G$ be a caterpillar and let $P=x_1\dots x_\ell$ be a longest path containing every vertex of degree $2$ or more. Note that, by maximality, $d(x_1)=d(x_\ell)=1$. We can produce a drawing of $G$ by first drawing $P$ as a zig-zag and then adding the degree-$1$ vertices adjacent to $x_i$ between $x_{i-1}$ and $x_{i+1}$. $\Box$

Lemma 2. Every graph $G$ in your class is acyclic.

Proof. Suppose $G$ contains the cycle $x_1y_1x_2y_2\dots x_ky_kx_1$ and suppose it has a drawing of the required form. W.l.o.g., $x_2$ is above $x_1$. But then we must have $y_2$ above $y_1$ since, otherwise, the lines $x_1y_1$ and $x_2y_2$ would cross. By induction, $x_{i+1}$ is above $x_i$ for all $i\in\{1, \dots, k-1\}$ and likewise for the $y$'s. But then any line $y_kx_1$ must either leave the region between the two columns of vertices or cross every other edge in the cycle. This contradicts our assumption that the graph has a proper drawing. $\Box$

Lemma 3. Every connected non-caterpillar is not in your class.

Proof. Let $G$ be a connected graph that is not a caterpillar. If it contains a cycle, it is not in your class by Lemma $2$, so we may assume it is a tree. If it is not a caterpillar, it must contain a vertex $x$ with distinct neighbours $y_1$, $y_2$ and $y_3$, each of which has degree at least  $2$.

Suppose we have a drawing of $G$ with the required properties. W.l.o.g., $y_2$ is above $y_1$ and $y_3$ is above $y_2$. Let $z\neq x$ be a neighbour of $y_2$. The edge $y_2z$ must cross $xy_1$ or $xy_3$, contradicting our assumption that the graph has a drawing of the required form. $\Box$

Theorem. Your class of graphs is exactly the class of forests each of whose components is a caterpillar.

Proof. Let $G$ be a graph. Clearly, $G$ is in your class if, and only if, every component is: if any component cannot be drawn as required, the whole graph cannot; if every component can be drawn as required, then the whole graph can be drawn by arranging the components one above the other. The result now follows by Lemmas $1$ and $3$. $\Box$

Corollary. Your class of graphs is the class of graphs that do not have $K_3$ or the subdivision of $K_{1,3}$ as a minor.

Proof. These are the obstructions for path-width $1$. $\Box$

These are essentially the obstructions you found: you need $K_3$ rather than $K_4$ because the latter would admit $K_3$ into the class; the subdivision of $K_{1,3}$ is exactly your second obstruction.

Answer 2

So, the following answer is what I came up with:

As you already mentioned, there are only two possible cases which cannot be rearranged.

The second case is no correct representation if we assume a bipartite graph, since Wikipedia defines a bipartite graph as: every edge connects a vertex in $U$ to one in $V$.

Edit: I misread the graph, sorry for that.

This leaves us only with the $K_{2,2}$ complete subgraph, which is the condition you want to avoid. Inversely, the sufficient condition is that your bipartite graph has no complete subgraph within itself.

To prove that any other subgraph is valid, you can imagine the following:

First, we assume that we have no edges and start with an arbitrary edge $e$. By adding the next edge, we have three possible cases:

The first case is that we have a node which neither starts nor ends at the same node as the first edge. This leaves us without any problem and we can continue inserting.

The second case is that we have a edge which - on its way - crosses another, already existing, edge. In this case we have to swap the vertex $V_1$ or $V_2$ (the one with the already existing edge) with one of the new edges $V_3$ or $V_4$, such that we continue fulfilling the criteria.

This assumes that we have no further edges starting or ending at the nodes to swap, which leads us to the following third case: After swapping one of the four Vertices $V1-V4$, we need to trace all other connections from the swapped Vertex.

Once again we can find only three solutions: Either we trace a ending connection, or repeat the step that we already took before (tracing all remaining steps). If we end up on an ending node, we can swap all of the traced nodes.

The last possible case will lead to a node which we already visited, which would leave us with a complete subgraph, which we can then reduce to the mentioned $K_{2,2}$ condition.

EDIT: To extend this proof to the second case, we have to look at the following conditions:

In general, if we have a subgraph with at least one hub (3 or more connections), it is "rather easy".

We cannot rearrange if we have the displayed case with more than two neighbors of higher degree than one ($\langle k\rangle > 1$). This is important because it provides is with the knowledge about further neighbors. We don't even have to trace them any further to avoid any circles (like the first case), but it is enought to check the immediate neighbors.

Since I myself have only slight knowledge in this area, but still want to provide you with a possible solution, I linked you one (hopefully) appropriate article

If anyone would name this problem, I'd be interested to learn, especially since I came up with this solution only by following up on thoughts from Fáry's theorem and complete bipartite subgraphs.