7
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

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:

alt text

Improve this answer
$\endgroup$
4
  • $\begingroup$ excellent. I suspected that book embeddings had something to do with this. But I'm still not clear about one thing: are you asserting that if I allow curves for edges, I can do precisely what I asked ? because with the example you gave above, it seems like even that would not be possible. $\endgroup$
    – Suresh Venkat
    Commented Nov 8, 2010 at 0:23
  • 1
    $\begingroup$ here is one way to see that the first assertion of David's answer is true. take any planar drawing of your graph on a sphere, and then draw a continuous simple closed curve that passes through all the vertices of your graph. now pull your curve along the surface of the sphere until it forms a great circle and at the same time stretch and smoosh the two regions the curve bounds so they become hemispheres. this will change the shape of your edges but will not change the fact that the drawing is planar. now all your vertices are on a line, which is actually more than what you asked for. $\endgroup$
    – Louigi Addario-Berry
    Commented Nov 8, 2010 at 0:34
  • $\begingroup$ actually, what i described gives something weaker than David's assertion but still stronger than what you asked for. it's not hard to get from what i described to david's assertion, though (but it will result in edges that are very spirally). $\endgroup$
    – Louigi Addario-Berry
    Commented Nov 8, 2010 at 0:36
  • $\begingroup$ The link to the image seems to be broken. $\endgroup$
    – The Amplitwist
    Commented Feb 9 at 9:15
3
$\begingroup$

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.)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .