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

Improve this question
$\endgroup$
1
  • $\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
    Commented Jan 14, 2012 at 13:32

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks David for your nice answer. It gives a good starting point for new ideas to work with. $\endgroup$
    – Etsch
    Commented Jan 16, 2012 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
    Commented Jan 16, 2012 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
    Commented Jan 16, 2012 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
    Commented Jan 16, 2012 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
    Commented Jan 17, 2012 at 7:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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