Get the adjacency matrix of the dual of a 3-connected $k$-regular $G$ without pen and paper

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 vertex I started three times for three 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?

Solutions Collecting From Web of "Get the adjacency matrix of the dual of a 3-connected $k$-regular $G$ without pen and paper"