Determine if a Graph is Toroidal

Question

A simple graph is toroidal if it can be drawn on the surface of a torus without any edges intersecting. Your task is to take a simple undirected graph via any reasonable method (adjacency matrix, edge vertex sets, etc.) and decide whether or not it is a toroidal graph. You should output one of two distinct values for each of the two decisions. You may choose what these values are.

This is code-golf so answers will be scored in bytes with less bytes being better.

Test Cases

Here K_n is the complete graph with n vertices and K_n,m is the complete bipartite graph.

Toroidal

• K₃

• K₇

• K_3,3

• The Peterson graph

• The Möbius Cantor graph

Not Toroidal

• K₈

Answer 1

Rust, 1210 1200 bytes

use std::collections::HashMap as H;type I=i64;type E=Vec<(I,I)>;fn d(g:&E)->bool{let mut s:Vec<(E,Vec<I>)>=vec![];for e in g{let(v,w)=e;let f=(*v,*w);let z=|x|s.iter().position(|p|p.1.contains(x));match(z(v),z(w)){(Some(i),Some(j))=>{if i!=j{let mut p=s.remove(i);let q=s.remove(j-(i<j)as usize);p.0.extend(q.0);p.1.extend(q.1);s.push(p)}else{s[i].0.push(f)}}(Some(i),_)=>{s[i].0.push(f);s[i].1.push(*w)}(_,Some(j))=>{s[j].0.push(f);s[j].1.push(*v)}_=>{s.push((vec![f], vec![*v, *w]))}}}s.iter().map(|h|{let mut p=H::new();let mut r=H::new();let mut i=0;for e in&h.0{let(v,w)=e;i+=2;p.insert(i-1,i);p.insert(i,i-1);r.entry(v).or_insert(vec![]).push(i-1);r.entry(w).or_insert(vec![]).push(i)}let mut r:Vec<Vec<I>>=r.values().cloned().collect();r.sort();let mut x=0;let m=r.iter().flat_map(|v|1..v.len()).fold(1,|p,n|p*n);for mut w in 0..m{let mut t=H::new();for u in&r{let mut v=u.clone();let s=v.pop().unwrap();let mut f=s;while v.len()>0{let o=v.remove(w%v.len());w/=v.len()+1;t.insert(f,o);f=o}t.insert(f,s);}let mut f=vec![];let mut n=0;for s in p.keys(){if!f.contains(s){n+=1;let mut c=s;loop{f.push(*c);c=&t[&p[c]];if c==s{break}}}}x=x.max(n)}1-(r.len()as I-g.len()as I+x as I)/2}).sum::<I>()<2}

A toroidal example: Try it online!

That's this toroidal graph:

A non-toroidal example: Try it online!

That's this non-toroidal graph:

The original code I wrote, before golfing, was the following. It has printouts so you can see what's happening:

use std::collections::HashMap;

#[derive(PartialEq, Eq, Hash, Clone, Copy, Debug)]
struct Vertex(u64);
type Edge = (Vertex, Vertex);
type Graph = Vec<Edge>;

fn full_genus(graph: &Graph) -> usize {
    componets(graph).iter().map(|g| genus(g)).sum()
}
fn genus(graph: &Graph) -> usize {
    #[derive(PartialEq, Eq, Hash, Clone, Copy, Debug, PartialOrd, Ord)]
    struct HalfEdge(usize);
    let mut edge_pairing: HashMap<HalfEdge, HalfEdge> = HashMap::new();
    let mut vertex_groups: HashMap<&Vertex, Vec<HalfEdge>> = HashMap::new();
    let mut i = 0;
    for edge in graph {
        let (vert1, vert2) = edge;
        let half1 = HalfEdge(i);
        i += 1;
        let half2 = HalfEdge(i);
        i += 1;
        edge_pairing.insert(half1, half2);
        edge_pairing.insert(half2, half1);
        vertex_groups.entry(vert1).or_insert(vec![]).push(half1);
        vertex_groups.entry(vert2).or_insert(vec![]).push(half2);
    }
    let mut vertex_groups: Vec<Vec<HalfEdge>> = vertex_groups.values().cloned().collect();
    vertex_groups.sort();
    println!("{:?}", edge_pairing);
    println!("{:?}", vertex_groups);

    let mut max_faces = 0;
    let num_rotations = vertex_groups
        .iter()
        .map(|v| v.len() - 1)
        .map(|n| {
            let mut prod = 1;
            for i in 0..n {
                prod *= i + 1;
            }
            prod
        })
        .fold(1, |p, n| p * n);
    println!("\nNum rotations: {}\n", num_rotations);
    for rotation_index in 0..num_rotations {
        let mut working_index = rotation_index;
        let mut rotation: HashMap<HalfEdge, HalfEdge> = HashMap::new();
        let mut pretty_rotation: Vec<Vec<HalfEdge>> = vec![];
        for group in &vertex_groups {
            let mut removal_group = group.clone();
            let start = removal_group.pop().unwrap();
            let mut from = start;
            let mut pretty_group = vec![from];
            while !removal_group.is_empty() {
                let index = working_index % removal_group.len();
                working_index /= removal_group.len();
                let to = removal_group.swap_remove(index);
                rotation.insert(from, to);
                pretty_group.push(to);
                from = to;
            }
            rotation.insert(from, start);
            pretty_rotation.push(pretty_group);
        }
        let mut seen_on_face: Vec<HalfEdge> = Vec::new();
        let mut num_faces = 0;
        for start_halfedge in edge_pairing.keys() {
            if !seen_on_face.contains(start_halfedge) {
                num_faces += 1;
                let mut current_halfedge = start_halfedge;
                loop {
                    seen_on_face.push(*current_halfedge);
                    let pair_halfedge = &edge_pairing[current_halfedge];
                    current_halfedge = &rotation[pair_halfedge];
                    if current_halfedge == start_halfedge {
                        break;
                    }
                }
            }
        }
        if num_faces > max_faces {
            max_faces = num_faces;
            let euler_characteristic: isize =
                vertex_groups.len() as isize - graph.len() as isize + max_faces as isize;
            let genus_num: isize = 1 - euler_characteristic / 2;
            println!(
                "Faces: {}, Genus <= {} on rotation {}",
                max_faces, genus_num, rotation_index
            );
            println!("{:?}\n", pretty_rotation);
        }
        if rotation_index % 1e7 as usize == 0 {
            println!("Faces: {} <= {} on rotation {}", num_faces, max_faces, rotation_index);
        }
    }
    let euler_characteristic: isize =
        vertex_groups.len() as isize - graph.len() as isize + max_faces as isize;
    let genus_num: isize = 1 - euler_characteristic / 2;
    assert!(genus_num >= 0);
    genus_num as usize
}

fn componets(graph: &Graph) -> Vec<Graph> {
    let mut graphs: Vec<(Graph, Vec<Vertex>)> = vec![];
    for edge in graph {
        let (vert1, vert2) = edge;
        let g_index1 = graphs.iter().position(|(_g, h)| h.contains(&vert1));
        let g_index2 = graphs.iter().position(|(_g, h)| h.contains(&vert2));
        match (g_index1, g_index2) {
            (Some(i1), Some(i2)) => {
                if i1 != i2 {
                    let (mut graph1, mut vs1) = graphs.remove(i1);
                    let new_i2 = if i1 < i2 { i2 - 1 } else { i2 };
                    let (graph2, vs2) = graphs.remove(new_i2);
                    graph1.extend(graph2);
                    vs1.extend(vs2);
                    graphs.push((graph1, vs1));
                } else {
                    graphs[i1].0.push(edge.clone());
                }
            }
            (Some(i1), None) => {
                graphs[i1].0.push(edge.clone());
                graphs[i1].1.push(vert2.clone());
            }
            (None, Some(i2)) => {
                graphs[i2].0.push(edge.clone());
                graphs[i2].1.push(vert1.clone());
            }
            (None, None) => {
                let edges = vec![edge.clone()];
                let vs = vec!(vert1.clone(), vert2.clone());
                graphs.push((edges, vs));
            }
        }
    }
    graphs.into_iter().map(|(g, _h)| g).collect()
}

fn main() {
    let graph = vec![
        (Vertex(0), Vertex(1)),
        (Vertex(0), Vertex(2)),
        (Vertex(0), Vertex(3)),
        (Vertex(0), Vertex(4)),
        (Vertex(0), Vertex(5)),
        (Vertex(1), Vertex(2)),
        (Vertex(1), Vertex(3)),
        (Vertex(1), Vertex(4)),
        (Vertex(1), Vertex(5)),
        (Vertex(2), Vertex(3)),
        (Vertex(2), Vertex(4)),
        (Vertex(2), Vertex(5)),
        (Vertex(3), Vertex(4)), 
        (Vertex(3), Vertex(5)),
    ];  
    let result = full_genus(&graph);
    println!("Result: {}", result);
}

This program finds the minimum genus surface that the given graph can be embedded in. A graph is toroidal if that genus is at most 1, the genus of the torus.

The code works by separating the graph into its connected components, finding their genii separately, and adding up the results.

To find the genus of a connected graph, I brute force search over all possible rotation systems of the graph, and figure out which one has the most faces. A rotation system is simply an ordering on the edges emerging from each vertex, saying what order those edges are in going around the vertex. Each rotation system has a straightforward minimum genus it can be embedded in, and having more faces directly corresponds to having lower genus. Since every possible embedding corresponds to some rotation system, if there is a toroidal embedding, my program will find the corresponding rotation system and declare that the graph is toroidal, and vice versa.

This program is very slow, because it searches through a number of rotation systems equal to the product over all degrees d of the vertices of (d-1)!. However, it can search through a little over 10 million such rotation systems per minute, so it can verify the toroidality or non-toroidality of simple graphs like the ones shown above.