2
$\begingroup$

Suppose you are given a list of vertices (with known positions) and their respective degrees, find any set of non-intersecting edges that satisfies the vertex degrees. Or, in other words, connect the dots in a way that each one has the specified number of connections. It's not necessary to find all solutions, the first one is enough. Equivalently: given a degree sequence, find a planar graph that has that degree sequence.

I'm not sure how to even approach this task, seems like I need to find all possible graph connections (it gets even harder because the connection order matters). I feel like there should be some greedy approach (like trying to connect each vertex the specified number of times), but I'm not sure how to make it check all possible ways eventually. enter image description here

Improve this question
$\endgroup$
6

1 Answer 1

Reset to default
1
$\begingroup$

Mathematical Approach

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 :

http://web.cse.msu.edu/~cse835/Papers/On%20realizing%20all%20simple%20graphs%20with%20a%20given.pdf

for realizing (listing) all graphs for a degree sequence. To list them efficiently, this paper gives a method with polynomial delay:

http://www.cs.elte.hu/egres/tr/egres-11-11.pdf

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:

  1. 'Reduce' the degree sequence in all possible ways to tree-realizable ones
  2. From the set of reduced sequences, generate trees
  3. Connect these trees up to full graphs, planar checking as you go

To do step 2, I found [this thesis][1] 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. [1]: https://digitalcollections.wesleyan.edu/object/ir-672

Improve this answer
$\endgroup$
5
  • $\begingroup$ I don't think this works. It's possible that the graph HH gives you is not planar, even though there exists another graph that is planar and would work. See, e.g., math.stackexchange.com/q/1056471/14578. Alternatively, if you enumerate all graphs with that degree sequence, that will give you correct results but I expect it could take exponential time in the worst case, so that doesn't seem like a good solution, either. $\endgroup$
    – D.W. ♦
    Nov 21, 2021 at 2:53
  • $\begingroup$ yes obviously. i did mention that. i have also added another link to a paper with an explicit complexity result (polynomial delay in output) $\endgroup$
    – gilleain
    Nov 21, 2021 at 19:36
  • $\begingroup$ Polynomial delay doesn't seem enough to give an efficient algorithm. If there are exponentially such graphs that are consistent with the degree sequence, then it still takes exponential time to list them all (despite the polynomial delay), and you may need to list them all to find if any of them are planar, so this still leads to an exponential-time algorithm, alas. $\endgroup$
    – D.W. ♦
    Nov 21, 2021 at 21:17
  • $\begingroup$ Fine. Indeed Kiraly's paper mentions this. I guess it depends on what the questioner wants to do. If they only care about a small number of examples, then the size of the output may not be a problem. $\endgroup$
    – gilleain
    Nov 22, 2021 at 11:31
  • $\begingroup$ Even if they only want one planar graph, this approach is still not efficient. You might have to explore exponentially many (non-planar) graphs before you find the first planar graph. $\endgroup$
    – D.W. ♦
    Nov 23, 2021 at 4:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.