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?
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.