[Math] Find a graph $G$ with 8 vertices such that $G$ and its complement are both planar.

Question

I have no problem producing a 8 vertices planar graph $G$, but I couldn't figure out how to find complement with $G$ that's also planar.

Is there any systematic way of drawing such graph? Thanks for any help.

Answer 1

Take an $8$-cycle $v_1v_2v_3v_4v_5v_6v_7v_8v_1$ and add two more edges $v_1v_5$ and $v_2v_6.$ The resulting graph $G$ is clearly planar. I leave it to you to verify that the complement $\overline G$ is also planar. ($\overline G$ is a cube with $6$ additional edges, namely, a diagonal drawn on each face.)

Methodology? It just seemed like a good idea to start with a maximal planar graph; the more edges in the graph, the fewer edges in the complement, and the easier it will be to draw the complement in the plane. So I took a cube (no particular reason, just because it's a nice planar graph with $8$ vertices) and triangulated each of the faces. The complement turned out to be a cycle plus two diagonals, which was planar and easy to describe.

P.S. To see that $G$ is planar, let $v_1=(0,0),\ v_2=(1,1),\ v_3=(1,2),\ v_4=(1,3),$
$v_5=(1,4),\ v_6 (2,4),\ v_7=(2,2),\ v_8=(2,0),$ and draw the edges $v_1v_2,\ v_2v_3,\ v_3v_4,\ v_4v_5,\ v_5v_6,\ v_6v_7,\ v_7v_8,\ v_8v_1,\ v_1v_5,\ v_2v_6$ as straight line segments.