Planar layouts of bipartite graphs - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T15:37:33Z http://mathoverflow.net/feeds/question/45211 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/45211/planar-layouts-of-bipartite-graphs Planar layouts of bipartite graphs Suresh Venkat 2010-11-07T21:05:01Z 2010-11-07T22:47:11Z <p>Instances of SAT induce a bipartite graph between clauses vertices and variable vertices, and for planar 3SAT, the resulting bipartite graph is planar. </p> <p>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. </p> <p>But maybe a weaker layout is possible. </p> <blockquote> <p>Is it possible to lay out any planar bipartite graph $G = (A \cup B, E)$ such that</p> <ul> <li>All vertices of $B$ are on a straight line</li> <li>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$.</li> </ul> </blockquote> <p>This seems to relate to <a href="http://mashfiquirabbi.110mb.com/files/thesis.pdf" rel="nofollow">track drawings of planar graphs</a>. </p> http://mathoverflow.net/questions/45211/planar-layouts-of-bipartite-graphs/45222#45222 Answer by Louigi Addario-Berry for Planar layouts of bipartite graphs Louigi Addario-Berry 2010-11-07T22:07:06Z 2010-11-07T22:12:50Z <p><b>Edit:</b> 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. </p> <hr> <p>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. </p> <p>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.)</p> http://mathoverflow.net/questions/45211/planar-layouts-of-bipartite-graphs/45226#45226 Answer by David Eppstein for Planar layouts of bipartite graphs David Eppstein 2010-11-07T22:37:16Z 2010-11-07T22:47:11Z <p>Any planar graph can be drawn with curves for the edges and its vertices in any position in the plane.</p> <p>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 <a href="http://en.wikipedia.org/wiki/Book_embedding" rel="nofollow">book embedding</a> 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 <a href="http://en.wikipedia.org/wiki/Goldner%25E2%2580%2593Harary_graph" rel="nofollow">Goldner–Harary graph</a>, and subdivide every edge, you will get a planar bipartite graph that cannot be drawn in the way you request.</p> <p>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:</p> <p><img src="http://www.ics.uci.edu/~eppstein/0xDE/cube-linear-bipartition.png" alt="alt text"></p>