Ideally, there would be an algorithm that directly and efficiently listed, from the degree sequence, only those graphs that are planar. However, that currently seems to be an open problem.
However your problem should be solvable using a combination of existing algorithms. There seem be at least two possibilities.
Filtering the output of HH with planarity checking
This way would combine Havel-Hakimi (HH), and planarity testing. The idea would be to use HH to check if any graph exists for the degree sequence. Then, use a planarity check on that graph to see if it is planar.
The only difficulty is that HH gives you the first possible graph for a sequence and not all of them. There is a more general algorithm here :
for realizing (listing) all graphs for a degree sequence. To list them efficiently, this paper gives a method with polynomial delay:
note that the total size of the output may be exponential.
Filtering Planar graphs by Degree Sequence
An alternative would to do the opposite : list all planar graphs on the number of vertices, and filter out (any) that match the degree sequence.
Although this sequence (https://oeis.org/A003094) grows very quickly, the approach outlined for plantri (https://users.cecs.anu.edu.au/~bdm/papers/plantri-full.pdf ) can be adapted to avoid generating examples with degrees above a specified maximum.
For some code that implements this approach, see https://github.com/mishun/plantri/blob/master/allowed_deg.c which is based on this paper : G. Brinkmann, B. D. McKay and U. von Nathusius, Backtrack search and look-ahead for the construction of planar cubic graphs with restricted face sizes, MATCH, 48 (2003) 163-177.
Weird hybrid approach
One final approach occurs to me, although it might have flaws that I cannot see:
- 'Reduce' the degree sequence in all possible ways to tree-realizable ones
- From the set of reduced sequences, generate trees
- Connect these trees up to full graphs, planar checking as you go
To do step 2, I found [this thesis] by Samuel Stern that gives what looks like an efficient algorithm, but the complexity given is not clear to me - $O(c_n(n^9))$ where $c_n$ is the number of non-isomorphic trees on n vertices.
The advantage of this approach would be that you should be able to check for planarity with each edge added to the trees, thus 'weeding out' any that cannot be planar.