Constructing a planar embedding from rigid vertices.

Question

I have a list of vertices with a cyclic ordering on their edges (rigid vertices).

Note on Rigid Vertices

I'm not sure how widespread the concept of rigid vertices are, and this helps illustrate them. As shown in the image, rotations ($1 \to 2$) and reflections ($2 \to 3$) of the edges are allowed, as these operations maintain the cyclic ordering. However ($3 \to 4$) changes the cyclic ordering of the vertex, so it's no longer the same rigid vertex.

I know for a fact that for this set of rigid vertices it is possible to give them a planar graph embedding and maintain their cyclic ordering, because in the problem I am working on, the vertices come from the crossings of a knot, and the edges come from the strands between crossings.

This is relatively easy to do by hand for small enough numbers of vertices. I do this by trial and error, drawing vertices with a particular orientation and seeing where they fit into what I have draw so far, and making changes if necessary. But I have no algorithm to do this, and it gets harder for larger numbers of vertices.

Example

The set of rigid vertices
$(L, H, A, G)$,
$(H, B, I, A)$,
$(B, F, C, E)$,
$(J, D, K, C)$,
$(D, L, E, K)$,
$(F, J, G, I)$

Embed as [Rigid Vertex Embedding]
(This example is relatively easy to do by hand.)

I'd like to find an algorithm to, knowing only the set of rigid vertices (as in the example) embed the vertices in a planar way without changing the cyclic ordering, preferably in a way that's implementable on a computer.

Answer 1

If the data comes from a knot (rather than a link), then this is the classic Gauss Word Problem. There are a number of linear-time algorithms to determine which vertices to flip to obtain a planar diagram (and there are also many for links). One paper I'm familiar with is

Rosenstiehl, Pierre; Tarjan, Robert E., Gauss codes, planar Hamiltonian graphs, and stack-sortable permutations, J. Algorithms 5, 375-390 (1984). ZBL0588.68034.

and at some point I implemented it (though I can't say I remember precisely how to use this code). The input data to the algorithm is essentially a DT (Dowker-Thistlethwaite) code, minus over/under crossing information. For example, here's a conversion of the data you provided into a DT code:

The specific input format in the linked program takes the DT code in the format

[Start 5, Start 8, Start 9, Start 6, Start 11, End 5,
 Start 3, Start 10, End 8, End 9, End 10, End 11]

(Each Start and End is like a pair of matching parentheses, the type of which is indexed by an integer. What the algorithm does is to put the parentheses into two classes so that, within each class, the parentheses are well-matched. You can read off the planar embedding in a direct way from which class each vertex got.)

If you don't care about linear time algorithms, then there is a naive exponential algorithm where you consider all $2^n$ flips of the $n$ vertices and compute the genus for each. It is straightforward computing the genus of a combinatorial map, since all you need to do is count the number of faces then calculate $1-\frac{1}{2}(V-E+F)$, assuming the diagram is connected. If this quantity is $0$, then you have found a set of flips that result in a planar embedding.

As for drawing, I've had success with doing a barycentric subdivision of the polyhedron associated with the planar embedding, then computing a Tutte embedding. The barycentric subdivision makes the edges bendable, which makes the embedding nicer. It also helps the graph satisfy the requirement of 3-connectivity for the Tutte embedding to be an embedding.

(I have code to do this, but unfortunately it's not in a shareable state yet. Once it is, hopefully later this year, I'll try to remember to update this answer.)