4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Tsuyoshi Ito Jan 14 '12 at 13:32
11
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks David for your nice answer. It gives a good starting point for new ideas to work with. $\endgroup$ – Etsch Jan 16 '12 at 9:45
  • $\begingroup$ 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? $\endgroup$ – Etsch Jan 16 '12 at 13:54
  • $\begingroup$ I'm pretty sure the example in my last sentence is correct. Maybe the paper you found is wrong? $\endgroup$ – David Eppstein Jan 16 '12 at 17:04
  • $\begingroup$ 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. $\endgroup$ – Etsch Jan 16 '12 at 21:18
  • $\begingroup$ 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. $\endgroup$ – David Eppstein Jan 17 '12 at 7:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.