# Reconstructing plane graphs from degree- and face-sequences

Let $G$ be a plane $3$-connected graph; so it partitions the plane into regions bounded by faces. Let $\mathrm{deg}_v$ be the sequence of vertex degrees of $G$, and $\mathrm{deg}_f$ be the sequence of the number of edges bounding each face, or, equivalently, the vertex degrees in the dual of $G$. Not always do $\mathrm{deg}_v$ and $\mathrm{deg}_f$ uniquely determine $G$. Here is a $2$-connected triangulated example, but similar $3$-connected examples can be constructed. (Notation: $5^2 4^3 3^4 2^2 = 5,5,4,4,4,3,3,3,3,2,2)$.

Nonisomorphic $2$-connected graphs with the same $\mathrm{deg}_v$ and $\mathrm{deg}_f$ sequences.

Q1. I am seeking an algorithm that will take as input $\mathrm{deg}_v$ and $\mathrm{deg}_f$ sequences, and output a plane graph $G$ that realizes these sequences (if they are compatible sequences).

Algorithms exist for realizing $\mathrm{deg}_v$ (see, e.g., Mathworld Graphic Sequences), but here I have (a) planarity, and (b) the dual degree sequence.

Q2. I have a sense that $\mathrm{deg}_v$ and $\mathrm{deg}_f$ "usually" determine a unique plane $G$ (if they are mutually consistent). Is this intuition correct? Can you suggest a precise formulation of the question?

• Regarding Q2, any two fullerenes on the same number vertices have the same degree and face-degree sequences. – Chris Godsil Sep 1 '18 at 3:36
• @ChrisGodsil: Could you explain a bit why, for those not fullerene aficionados. – Joseph O'Rourke Sep 1 '18 at 12:16
• O’Rourke: A fullerene is a cubic planar graph with exactly 12 face 5-gons ans the remaining faces 6-gons. There are lots of them, e.g., 1812 on 60 vertices according Brinkmann and Dress sciencedirect.com/science/article/pii/S0196677496908068 – Chris Godsil Sep 1 '18 at 15:33