3
\$\begingroup\$

This challenge arises from a claim made in a MathOverflow answer and a paper linked in that answer which seems to back up the claim:

Searching for triangular embeddings is much quicker than enumerating over all embeddings… In fact, Jungerman was able to find a triangular embedding of \$K_{18}-K_3\$ in about half an hour back in the 1970s.

Some definitions must be made here. A combinatorial embedding of a graph embedded in an orientable surface is an ordered adjacency list, where the list of neighbours for each vertex \$v\$ reflects their order when going around \$v\$ in a certain direction, which is the same for all vertices.

A combinatorial embedding corresponding to the above graph, embedded on the torus, is

0: 1 3 5 6
1: 0 6 3 2
2: 1 4 6 3
3: 0 2 1 4
4: 2 5 3
5: 0 4 6
6: 0 5 2 1

The neighbours are listed clockwise for all vertices. This embedding is the same as the one above because the neighbour lists for each vertex have only been cyclically permuted:

0: 3 5 6 1
1: 6 3 2 0
2: 1 4 6 3
3: 4 0 2 1
4: 3 2 5
5: 4 6 0
6: 2 1 0 5

However, if the neighbour list for vertex 5 was changed to 4 0 6, it would no longer be a combinatorial embedding because 4 0 6 is not a cyclic permutation of 0 4 6.

A triangular embedding is a combinatorial embedding satisfying rule R*, which when coupled with the vertex-edge-genus relationship that will be introduced later on guarantees that the embedding may be drawn on the surface without crossings and with all faces triangular:

If in the row for vertex i there appear the three consecutive vertices j k l in that order (reading forwards and wrapping around if necessary), in the row for vertex k there must appear the three consecutive vertices l i j in that order. This must hold for all adjacent vertex pairs i and k.

For example, the graph \$K_{10}-K_3\$ (a 10-vertex complete graph, or \$K_{10}\$, where the edges between 3 vertices have been removed, i.e. a \$K_3\$ is missing) has the following triangular embedding:

0: 1 7 6 2 8 5 4 9 3
1: 2 7 0 3 8 6 5 9 4
2: 3 7 1 4 8 0 6 9 5
3: 4 7 2 5 8 1 0 9 6
4: 5 7 3 6 8 2 1 9 0
5: 6 7 4 0 8 3 2 9 1
6: 0 7 5 1 8 4 3 9 2
7: 0 1 2 3 4 5 6
8: 0 2 4 6 1 3 5
9: 0 4 1 5 2 6 3

This embedding satisfies rule R*. For example, 9 5 3 appears in row 2, so 3 2 9 should appear in row 5, and it does.

It is not necessary to specify the genus of the surface on which a triangular embedding lives (can be drawn) on, since the graph contains all necessary information: count the number of edges \$E\$ and number of vertices \$V\$. Since all faces are triangles, the faces number \$F=2E/3\$. Then by Euler's formula the genus is $$\frac12(2-(V-E+F))=1+\frac{E/3-V}2$$ For example, the embedding of \$K_{10}-K_3\$ above has 10 vertices and 42 edges, so it lives on the surface of genus \$1+(14-10)/2=3\$.

While rule R* is fairly strong I still doubt that it makes searching for triangular embeddings – or proving their non-existence – much easier, especially since you still need to consider all permutations of neighbours for one vertex at the start. No code was provided in the MO answer or by Jungerman, so I'd like your help in "reconstructing" it.

Task

Write the that when given a graph in any reasonable format, determines whether a triangular embedding of the graph exists and outputs one such embedding if it does exist. If no embedding exists the program must indicate this in a halting manner (returning something else, raising an error, etc.) – it cannot run forever.

Your code must work in principle for an arbitrary input graph, which you may assume is 3-connected and would live on a surface of positive integer genus, calculated by \$1+\frac{E/3-V}2\$, if it could be triangularly embedded. (This implies that the input is non-planar.)

The code will be run on my Lenovo ThinkPad E14 Gen 2 laptop with an 8-core Intel Core i7 processor running Ubuntu 22.10. A program's score is the sum of time needed over the six inputs below – the lower the better. You may output the embedding in any reasonable format, as long as the order of neighbours for each vertex is clear. I encourage you to post the results for your code on your own machine for my reference.

Graphs with triangular embeddings

The graphs below are given as unordered adjacency lists.

  • \$K_{10}-C_9\$ (on genus 2), where \$C_9\$ is a 9-vertex cycle. I obtained an embedding of \$J(5,2)\$ from this by deleting 6 edges (see below):
0: 1 2 3 4 5 6 7 8 9
1: 0 2 3 4 6 7 8
2: 0 1 3 4 5 7 9
3: 0 1 2 5 6 8 9
4: 0 1 2 5 6 7 8
5: 0 2 3 4 6 7 9
6: 0 1 3 4 5 8 9
7: 0 1 2 4 5 8 9
8: 0 1 3 4 6 7 9
9: 0 2 3 5 6 7 8
  • \$K_{13}-K_3\$ (on genus 7) from Jungerman's paper, which says that a triangular embedding was computed in "about 2 seconds" on a PDP-15:
0: 1 2 3 4 5 6 7 8 9 10 11 12
1: 0 2 3 4 5 6 7 8 9 10 11 12
2: 0 1 3 4 5 6 7 8 9 10 11 12
3: 0 1 2 4 5 6 7 8 9 10 11 12
4: 0 1 2 3 5 6 7 8 9 10 11 12
5: 0 1 2 3 4 6 7 8 9 10 11 12
6: 0 1 2 3 4 5 7 8 9 10 11 12
7: 0 1 2 3 4 5 6 8 9 10 11 12
8: 0 1 2 3 4 5 6 7 9 10 11 12
9: 0 1 2 3 4 5 6 7 8 10 11 12
10: 0 1 2 3 4 5 6 7 8 9
11: 0 1 2 3 4 5 6 7 8 9
12: 0 1 2 3 4 5 6 7 8 9
  • \$K_{18}-K_3\$ (on genus 17) from Jungerman's paper, "about 25 minutes" on the same machine:
0: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
1: 0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
2: 0 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
3: 0 1 2 4 5 6 7 8 9 10 11 12 13 14 15 16 17
4: 0 1 2 3 5 6 7 8 9 10 11 12 13 14 15 16 17
5: 0 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17
6: 0 1 2 3 4 5 7 8 9 10 11 12 13 14 15 16 17
7: 0 1 2 3 4 5 6 8 9 10 11 12 13 14 15 16 17
8: 0 1 2 3 4 5 6 7 9 10 11 12 13 14 15 16 17
9: 0 1 2 3 4 5 6 7 8 10 11 12 13 14 15 16 17
10: 0 1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17
11: 0 1 2 3 4 5 6 7 8 9 10 12 13 14 15 16 17
12: 0 1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 17
13: 0 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 17
14: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 17
15: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
16: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
17: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Graphs without triangular embeddings

  • \$K_{4,2,2,2}\$ (on genus 2), a complete tetrapartite graph with partition sizes \$\{4,2,2,2\}\$ and the subject of the MathOverflow question:
0: 4 5 6 7 8 9
1: 4 5 6 7 8 9
2: 4 5 6 7 8 9
3: 4 5 6 7 8 9
4: 0 1 2 3 6 7 8 9
5: 0 1 2 3 6 7 8 9
6: 0 1 2 3 4 5 8 9
7: 0 1 2 3 4 5 8 9
8: 0 1 2 3 4 5 6 7
9: 0 1 2 3 4 5 6 7
0: 1 2 3 4 5 6
1: 0 2 3 4 7 8
2: 0 1 3 5 7 9
3: 0 1 2 6 8 9
4: 0 1 5 6 7 8
5: 0 2 4 6 7 9
6: 0 3 4 5 8 9
7: 1 2 4 5 8 9
8: 1 3 4 6 7 9
9: 2 3 5 6 7 8
  • \$K_{13}-K_6\$ (on genus 5) from Jungerman's paper:
0: 1 2 3 4 5 6 7 8 9 10 11 12
1: 0 2 3 4 5 6 7 8 9 10 11 12
2: 0 1 3 4 5 6 7 8 9 10 11 12
3: 0 1 2 4 5 6 7 8 9 10 11 12
4: 0 1 2 3 5 6 7 8 9 10 11 12
5: 0 1 2 3 4 6 7 8 9 10 11 12
6: 0 1 2 3 4 5 7 8 9 10 11 12
7: 0 1 2 3 4 5 6
8: 0 1 2 3 4 5 6
9: 0 1 2 3 4 5 6
10: 0 1 2 3 4 5 6
11: 0 1 2 3 4 5 6
12: 0 1 2 3 4 5 6
\$\endgroup\$
2
  • \$\begingroup\$ Is rule R* sufficient to guarantee a reordering is a valid embedding? \$\endgroup\$ Mar 7, 2023 at 21:40
  • \$\begingroup\$ @user1502040 Yes, with the additional conditions introduced later on (see edit). \$\endgroup\$ Mar 7, 2023 at 23:50

1 Answer 1

1
\$\begingroup\$

Python 3 + Google OR-Tools

A fairly direct encoding of the problem; takes a list of lists of adjacent indices for each variable. I suspect it might be possible to do better by introducing variables for the triangles, but then sub-cycles become a problem.

from ortools.sat.python import cp_model

def embed(g, log_search_progress=False):
    model = cp_model.CpModel()
    edges = [{} for _ in g]
    for i, g_i in enumerate(g):
        e = edges[i]
        for j in g_i:
            g_j = g[j]
            for k in g_i:
                if j == k:
                    continue
                if k not in g_j:
                    continue
                e[(j, k)] = model.NewBoolVar(f'e_{(j, k)}')
        index = {j: p for p, j in enumerate(g_i)}
        model.AddCircuit([(index[j], index[k], v) for (j, k), v in e.items()])
    for i, (g_i, e_i) in enumerate(zip(g, edges)):
        for j in g_i:
            for k in g_i:
                if (j, k) not in e_i:
                    continue
                v0 = e_i[(j, k)]
                for l in g_i:
                    if (k, l) not in e_i:
                        continue
                    v1 = e_i[(k, l)]
                    if l == j:
                        model.AddBoolOr([v0.Not(), v1.Not()])
                        continue
                    e_k = edges[k]
                    v2 = e_k[(l, i)]
                    v3 = e_k[(i, j)]
                    model.AddBoolOr([v0.Not(), v1.Not(), v2])
                    model.AddBoolOr([v0.Not(), v1.Not(), v3])
    solver = cp_model.CpSolver()
    if log_search_progress:
        solver.parameters.log_search_progress = True
    solver.parameters.linearization_level = 2
    status = solver.Solve(model)
    if status != 4:
        return None
    embedding = [[] for _ in g]
    for i, (e_i, emb_i) in enumerate(zip(edges, embedding)):
        succ = {}
        for (j, k), v in e_i.items():
            if solver.Value(v):
                succ[j] = k
        j = j0 = next(iter(succ))
        while True:
            emb_i.append(j)
            j = succ[j]
            if j == j0:
                break
    return embedding
\$\endgroup\$
3
  • \$\begingroup\$ What does OR stand for here? \$\endgroup\$
    – Seggan
    Mar 8, 2023 at 0:55
  • \$\begingroup\$ @Seggan Operations Research \$\endgroup\$ Mar 8, 2023 at 1:02
  • 1
    \$\begingroup\$ Your code breezes by the first five test cases but takes too long on the last (\$K_{13}-K_6\$). \$\endgroup\$ Mar 8, 2023 at 5:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.