Planar layouts of bipartite graphs - MathOverflow

Planar layouts of bipartite graphs

2010-11-07T21:05:01Z

Instances of SAT induce a bipartite graph between clauses vertices and variable vertices, and for planar 3SAT, the resulting bipartite graph is planar.

It would be very convenient if there was a planar layout that had all the variable vertices in one line and all the clause vertices in a straight line. This can't be done because such a graph would be outerplanar, and $K_{2,3}$ isn't.

But maybe a weaker layout is possible.

Is it possible to lay out any planar bipartite graph $G = (A \cup B, E)$ such that

All vertices of $B$ are on a straight line

A can be partitioned into $A_1 \cup A_2$ such that all vertices of $A_1$ are on a parallel straight line to the left of $B$, and all vertices of $A_2$ are on a parellel straight line to the right of $B$.

This seems to relate to track drawings of planar graphs.

Answer by Louigi Addario-Berry for Planar layouts of bipartite graphs

2010-11-07T22:07:06Z

Edit: When I posted this I was assuming you also wanted a straight-line drawing, which I now realize you did not say. The below relates only to straight-line drawings.

This is not possible. The $3$-cube is already a counterexample. Viewing the cube as the Hamming cube, up to symmetries there is only one way to place the middle two layers in the manner you suggest -- one must take ${100,010,001}\subset B$, ${110,011} \subset A_1$ and ${101}\subset A_2$. But then it is impossible to put $111$ in either $A_1$ or $A_2$ without creating crossing edges.

More generally, a counting argument should quite straightforwardly show that for large $n$, the proportion of planar graphs that satisfy your criteria is asymptotically small. (Using the fact that the number of labeled planar graphs on $n$ vertices is asymptotically $n! \cdot (27.22687\ldots)^n$ times lower order terms, which is a result of Gimenez and Noy.)

Answer by David Eppstein for Planar layouts of bipartite graphs

2010-11-07T22:37:16Z

Any planar graph can be drawn with curves for the edges and its vertices in any position in the plane.

But with straight line segment edges, it's not always possible, even for graphs in which every vertex in A has degree exactly two, and even if you relax the straight-line requirement for A and only require that the vertices in B be on a straight line. For, these graphs are exactly the graphs formed by subdividing every edge of an arbitrary planar graph G. And a drawing of this type, for a graph formed from G in this way, is exactly a two-page book embedding of G. But a planar graph G has a two-page book embedding only if edges can be added to it to make it Hamiltonian. So if you start with a graph G that is maximal planar and non-Hamiltonian, such as the Goldner–Harary graph, and subdivide every edge, you will get a planar bipartite graph that cannot be drawn in the way you request.

As an aside, relaxing the requirement that A be drawn on two lines parallel to the line through B does allow some additional graphs to be drawn, even though the above argument shows that it doesn't allow them all. For instance, Louigi has shown that the cube has no drawing on three parallel lines, but it does have one where B is on a straight line and A is on two sides of it: