MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 2 Added a note qualifying my answer.

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

show/hide this revision's text 1

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