6
$\begingroup$

Given the adjacency matrix $A$ of a $k$-regular planar 3-connected graph $G$ with $V$ vertices, so $A$ has dimension $V$. 3-connectedness is needed because, if the graph is 3-connected, then Whitney showed that the embedding, and thus the dual graph, is unique. (Source:Wikipedia)

How to get the adjacency matrix $\bar A$ of the dual of $G$ without drawing the dual graph?

Using Euler's formula $V+F=E+2$ and $kV=2E$ (because it's $k$-regular) we get the dimension of $\bar A$ to be $$ F=\left(\frac k2 -1\right)V+2, $$ but I have no idea how to fill this matrix. Can anyone help?

I assume $k=3$, since the case I'm mainly interested in are bicubic planar graphs consisting of squares ($4$-faces) and hexagons ($6$-faces). Further I assume $G$ to be hamiltonian, but if you can do it without, even better.

Here are my recent thoughts:

  1. Since I know how to get Returning Paths on Cubic Graphs Without Backtracking, I start with any vertex $v_0$ and propagate it like $$ Ap_r(A) = p_{r+1}(A) +2 p_{r-1}(A). $$ I should get back to the intial vertex, three times for three (possibly degenerate) values of $r$ according to the face degree of the faces adjacent to $v_0$. I'll do this for every vertex along the Hamilton cycle.

  2. Then my idea is to use Grinberg's Theorem to classify the faces (and therefore the vertices of the dual graph) whether they are inside (called $a_k$) or outside ($b_k$) the Hamilton cycle. It is not hard to see that $a_4+2a_6=\frac12V-1$.

But here I'm currently stuck to compile the information into the according adjacency matrix of the dual graph. Is this possible?

$\endgroup$
3
  • $\begingroup$ Something to consider: Let $G$ be self-dual. (You'll have to drop the $k$-regularity condition to get any non-trivial cases, but keep planarity and $3$-connectedness for uniqueness purposes.) If you can find a way to "see" that $\overline{A} = A$ in this case, then you'll be in a better position to handle your question. (I don't know of such a way, myself. There must be an algorithm somewhere that crunches through this stuff, though.) $\endgroup$
    – Blue
    Aug 4, 2013 at 22:30
  • $\begingroup$ I've been looking at the construction of a dual (planar) graph "without pen and paper", and discovered that it's a pretty interesting (non-trivial) problem. To the extent that known methods involve combinatorial search, it would be a stretch to claim these don't require pen-and-paper (arguably a computer is needed instead?). $\endgroup$
    – hardmath
    Aug 5, 2013 at 12:56
  • $\begingroup$ As advised on meta, I'll repost this question, which is close to this one, with the additional condition, that $G$ is 3-connected... $\endgroup$
    – draks ...
    May 2, 2017 at 10:45

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .