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?

  • 1
    $\begingroup$ Regarding Q2, any two fullerenes on the same number vertices have the same degree and face-degree sequences. $\endgroup$ – Chris Godsil Sep 1 '18 at 3:36
  • $\begingroup$ @ChrisGodsil: Could you explain a bit why, for those not fullerene aficionados. $\endgroup$ – Joseph O'Rourke Sep 1 '18 at 12:16
  • 4
    $\begingroup$ 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 $\endgroup$ – Chris Godsil Sep 1 '18 at 15:33

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.