How to convert a maximal planar graph to a regular planar multigraph?

Given a maximal planar graph (coming from the convex hull of a set of points on a sphere), I want to add edges until it is regular (all vertices touch the same number of edges), while keeping it planar. Multiple edges between the same pair of points are allowed, but edges starting and ending at the same point are not.

How can I find a set of edges to add which achieves this?

Any algorithm that can achieve this will be useful. Ideally it would also be a way to get there with the smallest number of edge additions, but a simple and reliable algorithm is more important here than being strictly minimal.

for example - here adding the red edges makes it 5-regular

This is a (hopefully more clearly defined) variation of my last question - From a triangulation of a sphere to a 4-regular planar graph in the minimum number of topological changes?

• This is better (I think), but it might be nice to include a gloss on "regular". If you still mean "all vertices have valence 4", then there's a problem: in the original triangulation, there might be a vertex with valence higher than $4$, e.g., draw a hexagon on the sphere and add the center point; it'll end up with valence $6$. – John Hughes Mar 28 at 15:41
• Thanks John. Yes, I've realised that all I actually need is for all vertices to have the same valence, even if that ends up being higher than 4. – D Piker Mar 28 at 15:48
• I am confused by this question as stated. If a planar graph is maximal then by definition you cannot add any more edges to it and keep the property of planarity. – Mike Mar 28 at 21:37
• I think I see what you are asking, but not sure. Are you looking to e.g., double or triple up some of the edges so that your planar graph becomes a planar multigraph [and you want an algorithm that does this adding as few parallel edges as possible]? Please advise. – Mike Mar 28 at 21:45
• Hi @Mike - Yes exactly as you say, there will need to some pairs of vertices connected by more than one edge, and I want to do this with as few new edges as possible. – D Piker Mar 28 at 22:43

I have two news for you. I’ll start from a good one.

Note that since the original graph $$G$$ is maximal, regularizing it we can add only copies of edges $$G$$.

If $$G$$ has and odd number of vertices an we are given a Hamiltonian cycle $$C$$ in $$G$$ then we can regularize $$G$$ as follows. Let $$V$$ be the set of vertices of the graph $$G$$. For each vertex $$v\in V$$ a graph $$C\setminus\{v\}$$ has a unique perfect matching $$M_v$$. It it easy to see when for each vertex $$u\in V$$ we add to the graph $$\deg u$$ many copies of $$M_u$$, degree of each vertex $$v\in V$$ will become $$\deg v+\sum_{u\in V\setminus\{v\} }\deg u=\sum_{u\in V} \deg u=2m,$$ where $$m$$ is a number of eges of the original graph $$G$$. In order to decrease the number of added egdes we can remove from them as many copies of $$C$$ as we can.

Unfortunately, the second news is that even a Hamiltonian triangulation (with even number of vertices) can be non-regularizable. Its construction is suggested by the following slide from “Hamiltonian Cycles in Triangulations” by Gunnar Brinkmann, Craig Larson, Jasper Souffriau, and Nico Van Cleemput.

Lemma follows from the observation that in a Hamiltonian cycle in the subdivided graph both neighbors of each vertex corresponding to a face of the basic graph are vertices of the basic graph. At the picture is drawn probably a simplest example of the basic triangulation which is a complete graph $$K_4$$ on four vertices with one subdivided face.

Let $$G$$ be any plane graph whose sets of vertices, edges, and faces are $$V$$, $$E$$, and $$F$$, respectively with $$n=|V|$$, $$m=|E|$$, and $$k=|F|$$. I claim that if $$k\ge n$$ then the face subdivision $$G’$$ of $$G$$ is non-regularizable. Indeed, assume that $$r$$ is a common vertex degree of a regularization of the graph $$G’$$. For the brevity we shall consider a vertex of $$G’$$ corresponding to a face $$f$$ of $$G$$ as this face. Recall that each such vertex is adjacent only to vertices of $$G$$. So when we increase a degree of $$f$$ adding an edge incident to $$f$$, we also increase degree of some vertex of $$G$$. In total we increase sum of degrees of faces of $$G$$ by $$\sum_ {f\in F} (r-\deg f) = kr-2m.$$ So the sum of degrees of vertices of $$G$$ will be at least $$kr-2m+\sum_{v\in V} \deg v+\sum_ {f\in F}\deg f= kr+2m.$$ But then an average degree of a vertex $$v\in V$$ will be at least $$(kr+2m)/n\ge (kr+2m)/k>r$$, a contradiction.

Since a graph $$K_4$$ has four vertices and four faces, its face subdivision $$K_4’$$ (see the picture below) is a simple example of a non-regularizable triangulation. It is Hamiltonian but a sequence of degrees of vertices along a Hamiltonian cycle is $$\dots, 3,6,3,6,\dots$$, so the regularization approach from the first part of the answer clearly fails for this graph.