Given a triangulation of a sphere (coming from the convex hull of some points on that sphere), I need to get to a graph with these points as the vertices, where each vertex is connected by edges to exactly 4 other vertices, and no pair of vertices is connected by more than 2 edges.
It also needs to be possible to draw this new graph on the sphere without edges crossing.
A trivial way of doing this would be to find a cycle through the vertices and connect each consecutive pair with 2 edges. However, I want to find the graph which deviates as little as possible from the input convex hull.
I'm thinking that by some sequence of adding, removing, or flipping edges, it should be possible to get from the triangulation to the 4-regular graph, and am interested in finding an algorithm which can do this in a small number of steps.
Is this equivalent to some known problem? or can anyone guide me on how this might be approached?
To give some context - the intended application is generating quad meshes which 'wrap' a 'skeleton' of lines, so that each segment is surrounded by a 4 sided tube, and I need to apply this partition of the sphere into quads at each node (similar to what is described in this paper: https://hal.inria.fr/hal-01532765v2/document, but looking for an approach which does not depend on the order in which edges are processed).
So once I have this 4-valent graph, I will take the dual to get a quadrangulation of the sphere at each node, then connect up the quads between connected spheres with 4 sided tubes.
I hope that's clear. Please ask if any part doesn't make sense, or you'd like images to explain it better.
Thank you