5
\$\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.

example graph

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 the same 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.

Instead of Rule R*, Rule Δ* may be used instead, which states that if j k appears in row i then k i appears in row j.

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 24.04. 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

Timings for this answer:

K_10 - C_9: 0.0551433 s
K_13 - K_3: 0.724351
K_18 - K_3: 3.24007

K_4,2,2,2 : 0.0497883 s
J(5,2)    : 0.00700506
K_13 - K_6: 39.852
Improve this question
\$\endgroup\$
4
  • \$\begingroup\$ Is rule R* sufficient to guarantee a reordering is a valid embedding? \$\endgroup\$
    – user1502040
    Commented Mar 7, 2023 at 21:40
  • \$\begingroup\$ @user1502040 Yes, with the additional conditions introduced later on (see edit). \$\endgroup\$
    – Parcly Taxel
    Commented Mar 7, 2023 at 23:50
  • \$\begingroup\$ Can you add the timings for the answer you have to the question? That will give other people something to aim for. \$\endgroup\$
    – Simd
    Commented Oct 4 at 9:14
  • 1
    \$\begingroup\$ @Simd Done.\${}\$ \$\endgroup\$
    – Parcly Taxel
    Commented Oct 4 at 15:25

1 Answer 1

Reset to default
2
\$\begingroup\$

Python 3 + Google OR-Tools + NetworkX

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

from itertools import product
import networkx as nx
from ortools.sat.python import cp_model

def embed(G, log=False):
    model = cp_model.CpModel()
    litmap = {}
    for i in G:
        e = {}
        for j in G[i]:
            for k in nx.common_neighbors(G,i,j):
                litmap[(i,j,k)] = e[(j,k)] = model.NewBoolVar(f"{i}_{j},{k}")
        enum = {j: v for (v,j) in enumerate(G[i])}
        model.AddCircuit([(enum[j], enum[k], l) for ((j,k),l) in e.items()])
    for i in G:
        for k in G[i]:
            for (j,l) in product(nx.common_neighbors(G,i,k), repeat=2):
                b0 = litmap[(i,j,k)]
                b1 = litmap[(i,k,l)]
                if j == l:
                    model.AddBoolOr(b0.Not(), b1.Not())
                else:
                    model.AddBoolOr(b0.Not(), b1.Not(), litmap[(k,l,i)])
                    model.AddBoolOr(b0.Not(), b1.Not(), litmap[(k,i,j)])
    solver = cp_model.CpSolver()
    solver.parameters.log_search_progress = log
    solver.parameters.linearization_level = 2
    if solver.Solve(model) != 4:
        return None
    res = {}
    for i in G:
        rd = {j: k for ((h,j,k),l) in litmap.items() if i == h and solver.value(l)}
        rotation = [next(iter(rd))]
        while True:
            s = rd[rotation[-1]]
            if s == rotation[0]:
                break
            rotation.append(s)
        res[i] = rotation
    return res
Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ What does OR stand for here? \$\endgroup\$
    – Seggan
    Commented Mar 8, 2023 at 0:55
  • \$\begingroup\$ @Seggan Operations Research \$\endgroup\$
    – user1502040
    Commented Mar 8, 2023 at 1:02
  • \$\begingroup\$ @ParclyTaxel It runs fast for all cases for me. I get INFEASIBLE for (K13−K6 ) after 20 seconds. Is that what is expected? \$\endgroup\$
    – Simd
    Commented Oct 4 at 14:01
  • \$\begingroup\$ I have taken the liberty of tidying up and generalising your code (the graph vertices no longer have to be the first nonnegative integers). \$\endgroup\$
    – Parcly Taxel
    Commented Oct 5 at 6:30

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.