Graph embedding constrained to a surface?

Have been contemplating it for a while, but did not dare to post as I felt like this must be a major undertaking to implement. Then saw the excellent answers to a recent question RegionPlot3D KnotData and decided to try anyway.

Given a surface via, say, implicit or parametric equation, and a graph, given, say, as a Graph object, is there a way to draw this graph on that surface with, say, analog of the SpringElectricalEmbedding or something like that?

As an ultimate goal, one would think of creating programmatically optimal versions of, e. g., this fantastic image

from "Patterns on the genus-3 Klein quartic" by Carlo H. Séquin.

For a specific goal of mine – under one of the questions on mathoverflow, there is a gluing scheme

for a graph on a genus 4 surface which in principle I could concoct but it would be ugly. I wonder if it could be done optimally using elastic string tension modeling possibilities of existing Mathematica functions.