Optimal embedding of a graph into a given manifold

Question

Suppose a graph with 4 vertices and 4 edges, as shown below:

   A----B
   |    |
   C----D

To embed this graph into the 2-dimensional sphere $S^2$, which can be thought of as the surface of a ball in 3-dimensional space. Now if we want to find a smooth embedding $f: G \rightarrow S^2$ that minimizes the maximum curvature of the curves that represent the edges of the graph. One possible smooth embedding of the given graph into the 2-dimensional sphere $S^2$ is shown below:

       A
     /   \
    /     \
   B-------D
    \     /
     \   /
       C

But if the graph has many vertices and edges, finding an optimal embedding that minimizes the maximum curvature of the curves that represent the edges of the graph can become a computationally challenging problem. And if we use some optimal or heuristic algorithm, then one issue is that the optimal embedding of a graph into a given manifold may depend on the specific metric or curvature of the manifold. For example, the optimal embedding of a graph into a sphere may be different from the optimal embedding into a hyperbolic space. Therefore, it can be challenging to choose an appropriate manifold for the graph, especially if the manifold is not known a priori. For example:

Consider the complete graph on four vertices, K4, which has six edges. We want to embed this graph into a two-dimensional manifold, either a sphere or a hyperbolic plane, such that the edges are mapped to smooth curves that do not intersect each other except at the vertices.

For the sphere, we can use the stereographic projection to embed K4 onto a hemisphere of the sphere. Specifically, we can map the vertices of K4 to four points on the equator of the sphere, and then project the hemisphere onto a plane using a central projection. The resulting embedding of K4 onto the plane is shown below:

      O---O
     / \ / \
    /   X   \
   O---O---O

Here, the vertices of K4 are labeled O and the intersections of edges are labeled X. The edges of K4 are mapped to circular arcs in the plane that intersect each other at the vertices. The curvature of each arc is constant and equal to 1/r, where r is the radius of the sphere.

For the hyperbolic plane, we can use the Poincaré disk model to embed K4 onto the unit disk. Specifically, we can map the vertices of K4 to four points on the boundary of the disk, and then use hyperbolic isometries to map the disk so that the edges of K4 are mapped to geodesic segments in the hyperbolic plane. The resulting embedding of K4 onto the Poincaré disk is shown below:

      O---O
     / \ / \
    /   X   \
   O---O---O

Here, the vertices of K4 are labeled O and the intersections of edges are labeled X. The edges of K4 are mapped to hyperbolic geodesics in the disk that intersect each other at the vertices. The curvature of each geodesic is constant and equal to -1/r^2, where r is the radius of the disk.

As we can see from this example, the optimal embedding of a graph into a given manifold may depend on the specific metric or curvature of the manifold. The optimal embedding of K4 onto the sphere and onto the hyperbolic plane is different, even though the graph itself is the same. Then are there any mathematical methods or tools for solving such problem? i.e., methods to solve the problem of finding an optimal embedding of a graph into a given manifold, even when the optimal embedding depends on the specific metric or curvature of the manifold?