# On planarity in two related graphs

Let $A$ be an $(n\times n)$-matrix with entries from $\{0,1\}$ and $B$ its biadjacency matrix $B = \begin{pmatrix} 0 & A\\ A^t & 0 \end{pmatrix}$.

My simple question is: Is there a relationship between the planar-property of the graph $\mathcal{G}_A$ (the graph constructed from the matrix $A$) and $\mathcal{G}_B$? Note that the graph $\mathcal{G}_B$ is necessarily undirected and loop-free.

(A good answer would be, e.g., that if $\mathcal{G}_A$ is planar, $A$ has to have some additional properties therewith $\mathcal{G}_B$ will be also planar)

Update: A property $\mathcal{G}_A$ must have therewith planarity passes on to $\mathcal{G}_B$ is to be bipartite. In that case $\mathcal{G}_B$ is the graph that consists of two disconnected copies of $\mathcal{G}_A$.

• An easy observation: if all the diagonal elements of A are 1 and G_B is planar, then G_A is planar because G_A is a contraction of G_B (plus self-loops). – Tsuyoshi Ito Jan 14 '12 at 13:32

$\mathcal{G}_B$ is the bipartite double cover of $\mathcal{G}_A$. So it has twice as many vertices and edges, and if $\mathcal{G}_A$ has an embedding with $x$ even faces and $y$ odd faces then $\mathcal{G}_B$ has an embedding (possibly on a nonplanar surface) with $2x+y$ faces, formed by making two copies of each even face and replacing each odd face by its double. Therefore, by Euler's formula, when the embedding of $\mathcal{G}_A$ is planar, the genus of $\mathcal{G}_B$ is at most $(y-2)/2$. In particular, if $\mathcal{G}_A$ is already bipartite, $\mathcal{G}_B$ consists of two disjoint copies of $\mathcal{G}_A$, and if $\mathcal{G}_A$ has only two odd faces then $\mathcal{G}_B$ will still be planar.
This is not a complete characterization: It might also be possible for $\mathcal{G}_B$ to be planar in some other cases, by using a different embedding from the one derived from $\mathcal{G}_A$. For instance, if $\mathcal{G}_A=K_4$, then $\mathcal{G}_B$ is a cube, and is planar, but the embedding derived from the planar embedding of $\mathcal{G}_A$ is a toroidal embedding of the cube with four hexagonal faces (the four equators of a standard cube) instead of the usual planar embedding with six square faces.
Some planar graphs $\mathcal{G}_A$ will definitely give nonplanar graphs $\mathcal{G}_B$. For instance, if $\mathcal{G}_A$ is the graph of the regular dodecahedron, its bipartite double cover is the cubic symmetric graph on 40 vertices, which is nonplanar. In the other direction, it is also possible for $\mathcal{G}_B$ to be planar even when $\mathcal{G}_A$ is nonplanar; for instance, if $\mathcal{G}_A$ is the nonplanar graph formed from $K_{3,3}$ by subdividing the edges of a 6-cycle, then $\mathcal{G}_B$ is the planar graph of the hexagonal prism (with both of its 6-cycles subdivided in the same way).
• But i am not sure about your last sentence. Meanwhile is found a paper which states that the bipartite double cover operation preserves non-planarity but does not preserve planarity. So the bipartite double cover of $K_{3,3}$ must be (and indeed it is) non-planar. Or do is missunderstand your sentence? – Etsch Jan 16 '12 at 13:54
• The matrix A in your SAGE code doesn't subdivide the edges of a hexagon in $K_{3,3}$ as I said to do, does it? If you did you should have a matrix of dimension 12, not 6. – David Eppstein Jan 17 '12 at 7:26