# From a triangulation of a sphere to a 4-regular planar graph in the minimum number of topological changes?

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

• You wrote "and no pair of vertices is connected by more than 2 edges", so it's OK for there to be two edges between some pair of vertices? You're willing to let bi-gons be bi-gons? – John Hughes Mar 27 at 14:18
• ha!, yes - I'm happy with bi-gons. For instance, in figure 3(c) in the paper linked above, each quad shares 2 edges with each of its neighbours - so it is the dual of a graph where each pair of points is connected by 2 edges. – D Piker Mar 27 at 14:20
• On a more serious note...what do you mean by "deviates as little as possible from the input CHULL"? Largest possible number of shared edges? Largest possible number of shared regions? Minimax alteration of region shapes (so that changing a 2-gon to a 12-gon would be 'very bad')? Without some sense of your goals here, it's tough to even think about an answer. It may be that by carefully formulating your goal, you find that you've answered your own question. :) – John Hughes Mar 27 at 14:22
• Thanks, that's a good question, and I guess I haven't figured out how to define precisely what I'm after here. For the application it is good that the shapes do not change very much from the convex hull, to avoid the resulting tubes becoming very twisted. – D Piker Mar 27 at 14:27
• I've made a new question that I hope is clearer: math.stackexchange.com/questions/3166035/… – D Piker Mar 28 at 15:37