<p>$\mathcal{G}_B$ is the <a href="http://en.wikipedia.org/wiki/Bipartite_double_cover">bipartite double cover</a> 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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2012-01-16T09:45:56.857Z
Thanks David for your nice answer. It gives a good starting point for new ideas to work with.
Etsch
CC BY-SA 3.0
2012-01-16T13:54:45.360Z
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
CC BY-SA 3.0
2012-01-16T17:04:33.710Z
I'm pretty sure the example in my last sentence is correct. Maybe the paper you found is wrong?
David Eppstein
CC BY-SA 3.0
2012-01-16T21:18:02.427Z
Its looks a bit strange, but the title of the paper is "Research on the Non-planarity about the Tensor Product of Graphs". If i test this using SAGE:
A = matrix(ZZ,6,[0,0,0,1,1,1, 0,0,0,1,1,1, 0,0,0,1,1,1, 1,1,1,0,0,0, 1,1,1,0,0,0, 1,1,1,0,0,0]);
G = Graph(A);
BG = BipartiteGraph(A);
print "planar(G): ",G.is_planar(); 
print "planar(BG): ",BG.is_planar();
i get two times "false" as the answer.
Etsch
CC BY-SA 3.0
2012-01-17T07:26:45.480Z
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
CC BY-SA 3.0
2012-01-17T12:20:20.610Z
Yes, sorry my fault. I reconstructed the graph now and indeed $\mathcal{G}_A$ is nonplanar, but $\mathcal{G}_B$ is. It seems that the paper i found is wrong.
Etsch
CC BY-SA 3.0
2012-01-14T21:15:50.150Z
2012-01-15T07:17:37.003Z
2012-01-15T07:17:37.003Z
David Eppstein
<p>Let $A$ be an $(n\times n)$-matrix with entries from $\{0,1\}$ and $B$ its biadjacency matrix $B = \begin{pmatrix} 0 &amp; A\\ A^t &amp; 0 \end{pmatrix}$. </p>

<p><em>My simple question is:</em> 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.</p>

<p>(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)</p>

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

CC BY-SA 3.0
2012-01-14T13:32:59.883Z
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
<graph-theory><matrices><planar-graphs>
On planarity in two related graphs
Etsch
# On planarity in two related graphs

(Asked by: username_0 on 2012-01-13)

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

**Tags:** graph-theory, matrices, planar-graphs

> **Comments:**
> **username_1**: 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).  

---

## 1 answers

### Answer by username_2 on 2012-01-14. Score: 11

$\mathcal{G}\_B$ is the [bipartite double cover](http://en.wikipedia.org/wiki/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).

> **Comments:**
> **username_0**: Thanks David for your nice answer. It gives a good starting point for new ideas to work with.  
> **username_0**: 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?  
> **username_2**: I'm pretty sure the example in my last sentence is correct. Maybe the paper you found is wrong?  
> **username_0**: Its looks a bit strange, but the title of the paper is "Research on the Non-planarity about the Tensor Product of Graphs". If i test this using SAGE: A = matrix(ZZ,6,[0,0,0,1,1,1, 0,0,0,1,1,1, 0,0,0,1,1,1, 1,1,1,0,0,0, 1,1,1,0,0,0, 1,1,1,0,0,0]); G = Graph(A); BG = BipartiteGraph(A); print "planar(G): ",G.is_planar();  print "planar(BG): ",BG.is_planar(); i get two times "false" as the answer.  
> **username_2**: 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.  
> **username_0**: Yes, sorry my fault. I reconstructed the graph now and indeed $\mathcal{G}_A$ is nonplanar, but $\mathcal{G}_B$ is. It seems that the paper i found is wrong.  

---

