Cayley Graphs: Visualizing Algebraic Structure

Cayley Graphs: Visualizing Algebraic Structure | Research | Tobias Weiss

Cayley graphs bridge abstract algebra and visual representation — they turn groups into graphs, revealing structure through geometry. This article explores Cayley graphs from multiple perspectives: formal definitions, algorithmic construction, and visualization techniques spanning 2D planar layouts to interactive 3D environments.

Formal Definition

A Cayley graph ( \Gamma(G, S) ) is a directed graph that encodes the structure of a group ( G ) with respect to a generating set ( S ).

Components

Vertices: Each vertex represents a group element ( g \in G )
Edges: For each generator ( s \in S ) and each vertex ( g ), there is a directed edge from ( g ) to ( gs )

Notation

( G ): The underlying group (finite or infinite)
( S ): The generating set (typically symmetric: ( S = S^ ))
( \Gamma(G, S) ): The Cayley graph
( (g, gs) ): Directed edge from vertex ( g ) to vertex ( gs ) labeled by generator ( s )

Properties

Cayley graphs inherit important properties from the group structure:

| Property | Group-theoretic meaning | Graph-theoretic consequence | | --------------------- | ------------------------------------------------------------------------------- | ------------------------------------------------- | ----------------- | ----------- | --- | ------------------------------------ | | Vertex-transitive | For any ( g, h \in G ), there exists ( x \in G ) such that ( xg = h ) | Automorphism group acts transitively on vertices | | Regular degree | Each vertex has ( | S | ) outgoing edges | Graph is ( | S | )-regular (if ( S ) is symmetric) | | Connected | ( S ) generates ( G ) | Any vertex reachable from identity via generators | | Bipartite | ( S \subseteq G \setminus G^2 ) (no generator is a product of two generators) | Graph is bipartite (if condition holds) |

Example: Symmetric Group S₃

The symmetric group ( S_3 ) (permutations of 3 elements) with generators ( {(12), (123)} ).

Group elements (6 total)

( e ): Identity ( () )
( a ): Transposition ( (12) )
( b ): 3-cycle ( (123) )
( b^2 ): ( (132) )
( ab ): ( (23) )
( ab^2 ): ( (13) )

Generating set

( S = {a, b, b^} = {(12), (123), (132)} )

Cayley graph construction

Each vertex represents one of the 6 permutations. Edges are labeled by generators:

Loading diagram...

The resulting graph is:

6 vertices (one per permutation)
9 edges (3 outgoing from each vertex)
Vertex-transitive (automorphism group is S₃)
Non-planar (contains K_ minor)

Visualization Approaches

2D Planar Embeddings

For groups whose Cayley graphs are planar, we can embed them in 2D space without edge crossings.

Force-directed layout

// Force-directed layout using D3
function layoutCayleyGraph(vertices, edges) {
  const simulation = forceSimulation(vertices)
    .force(
      "link",
      forceLink(edges)
        .id((d) => d.id)
        .distance(100),
    )
    .force("charge", forceManyBody().strength(-300))
    .force("center", forceCenter(width / 2, height / 2));

  simulation.on("tick", () => {
    svg
      .selectAll("line")
      .data(edges)
      .attr("x1", (d) => d.source.x)
      .attr("y1", (d) => d.source.y)
      .attr("x2", (d) => d.target.x)
      .attr("y2", (d) => d.target.y);

    svg
      .selectAll("circle")
      .data(vertices)
      .attr("cx", (d) => d.x)
      .attr("cy", (d) => d.y);
  });
}

Spectral layout (Laplacian eigenvectors)

For groups with nice structure, the first non-trivial eigenvectors of the graph Laplacian provide 2D coordinates.

import numpy as np
import scipy.linalg as la

def spectral_layout(adjacency_matrix):
  # Compute Laplacian: L = D - A
  degrees = np.sum(adjacency_matrix, axis=1)
  laplacian = np.diag(degrees) - adjacency_matrix

  # Compute eigenvectors
  eigenvalues, eigenvectors = la.eigh(laplacian)

  # Skip first (zero eigenvalue), use next two
  x = eigenvectors[:, 1]
  y = eigenvectors[:, 2]

  return list(zip(x, y))

3D Spatial Visualizations

For non-planar or large Cayley graphs, 3D visualization reveals structure that 2D hides.

Three.js visualization

import * as THREE from "three";
import { OrbitControls } from "three/examples/jsm/controls/OrbitControls.js";

function visualizeCayleyGraph3D(group, generators) {
  // Setup scene
  const scene = new THREE.Scene();
  const camera = new THREE.PerspectiveCamera(75, width / height, 0.1, 1000);
  const renderer = new THREE.WebGLRenderer({ antialias: true });

  // Controls for rotation/zoom
  const controls = new OrbitControls(camera, renderer.domElement);

  // Create vertices (spheres)
  const vertices = group.elements.map((element, i) => {
    const geometry = new THREE.SphereGeometry(0.5, 32, 32);
    const material = new THREE.MeshPhongMaterial({ color: 0x4488ff });
    const sphere = new THREE.Mesh(geometry, material);

    // Position in 3D using spherical layout
    const theta = (2 * Math.PI * i) / group.order;
    const phi = Math.acos(1 - (2 * i) / group.order);
    const r = 10;

    sphere.position.set(
      r * Math.sin(phi) * Math.cos(theta),
      r * Math.sin(phi) * Math.sin(theta),
      r * Math.cos(phi),
    );

    scene.add(sphere);
    return sphere;
  });

  // Create edges (cylinders)
  generators.forEach((generator, genIndex) => {
    const color = new THREE.Color().setHSL(genIndex / generators.length, 1, 0.5);

    group.elements.forEach((source, i) => {
      const target = source.multiply(generator);

      const geometry = new THREE.CylinderGeometry(0.1, 0.1, 1);
      const material = new THREE.MeshPhongMaterial({ color });

      const edge = new THREE.Mesh(geometry, material);
      edge.position.copy(vertices[i].position);
      edge.lookAt(vertices[target.index].position);
      edge.rotateX(Math.PI / 2);

      scene.add(edge);
    });
  });

  return { scene, camera, renderer, controls };
}

WebXR immersive visualization

// WebXR-compatible 3D Cayley graph visualization
async function immersiveCayleyGraph(group, generators) {
  // Initialize WebXR
  const xrSession = await navigator.xr.requestSession("immersive-vr");

  // Create large-scale graph in 3D space
  const scene = new THREE.Scene();

  // Walkable floor
  const floor = new THREE.Mesh(
    new THREE.PlaneGeometry(50, 50),
    new THREE.MeshStandardMaterial({ color: 0x333333 }),
  );
  floor.rotation.x = -Math.PI / 2;
  scene.add(floor);

  // Group vertices at walking height
  const graphGroup = new THREE.Group();
  graphGroup.position.set(0, 1.5, 0); // Eye level
  scene.add(graphGroup);

  // Interactive exploration
  const controller = renderer.xr.getController(0);
  controller.addEventListener("select", () => {
    // Highlight generator when selected
    const raycaster = new THREE.Raycaster();
    raycaster.setFromController(controller);

    const intersects = raycaster.intersectObjects(graphGroup.children);
    if (intersects.length > 0) {
      const vertex = intersects[0].object;
      highlightVertexAndEdges(vertex);
    }
  });
}

Animation: Group Multiplication

Visualize how group multiplication moves through the Cayley graph.

function animateMultiplication(startVertex, generator) {
  const targetVertex = group.multiply(startVertex, generator);

  // Animate transition
  const timeline = gsap.timeline();

  timeline.to(startVertex.position, {
    x: targetVertex.position.x,
    y: targetVertex.position.y,
    z: targetVertex.position.z,
    duration: 1,
    ease: "power2.inOut",
  });

  // Highlight traversed edge
  const edge = findEdge(startVertex, targetVertex, generator);
  timeline.to(
    edge.material,
    {
      emissive: 0xff0000,
      emissiveIntensity: 0.5,
      duration: 0.5,
    },
    0,
  );

  timeline.to(
    edge.material,
    {
      emissiveIntensity: 0,
      duration: 0.5,
    },
    0.5,
  );
}

Algorithmic Construction

Finite groups

For finite groups, we can enumerate all group elements and build the graph explicitly.

def build_cayley_graph_finite(group, generators):
  """
  Build Cayley graph for finite group.

  Args:
    group: Finite group (e.g., from sageall or custom implementation)
    generators: List of generating set elements

  Returns:
    networkx.DiGraph representing the Cayley graph
  """
  import networkx as nx

  G = nx.DiGraph()

  # Add vertices (group elements)
  for element in group:
    G.add_node(str(element), label=str(element))

  # Add edges (generator multiplications)
  for source in group:
    for generator in generators:
      target = source * generator

      G.add_edge(
        str(source),
        str(target),
        label=str(generator),
        generator=str(generator)
      )

  return G

Infinite groups (finitely generated)

For infinite groups like ( \mathbb^n ), we need different strategies.

Bounded region visualization

def build_cayley_graph_infinite_bounded(generators, bounds):
  """
  Build bounded Cayley graph for infinite group.

  Only includes vertices within specified bounds from identity.
  """
  import networkx as nx

  G = nx.DiGraph()

  # BFS from identity until bounds exceeded
  from collections import deque

  identity = tuple([0] * len(generators))  # Assuming Z^n
  queue = deque([identity])
  visited = {identity}

  while queue:
    current = queue.popleft()

    # Check bounds
    if any(abs(x) > b for x, b in zip(current, bounds)):
      continue

    # Add vertex
    G.add_node(str(current), label=str(current))

    # Add edges and explore neighbors
    for i, generator in enumerate(generators):
      # Add generator (positive direction)
      neighbor = tuple(
        current[j] + (1 if i == j else 0)
        for j in range(len(current))
      )

      if neighbor not in visited:
        visited.add(neighbor)
        queue.append(neighbor)

      G.add_edge(
        str(current),
        str(neighbor),
        label=f"+g{i+1}",
        generator=f"g{i+1}"
      )

      # Add inverse (negative direction)
      inverse_neighbor = tuple(
        current[j] - (1 if i == j else 0)
        for j in range(len(current))
      )

      if inverse_neighbor not in visited:
        visited.add(inverse_neighbor)
        queue.append(inverse_neighbor)

      G.add_edge(
        str(current),
        str(inverse_neighbor),
        label=f"-g{i+1}",
        generator=f"g{i+1}"
      )

  return G

Group presentation parsing

Parse group presentations (e.g., ( \langle a, b \mid a^2 = b^3 = (ab)^2 = e \rangle )) and construct Cayley graphs.

def parse_group_presentation(presentation_str):
  """
  Parse group presentation string.

  Example: "a,b | a^2, b^3, (ab)^2"

  Returns:
    generators: list of generator symbols
    relations: list of relation strings
  """
  generators_str, relations_str = presentation_str.split('|')

  generators = [g.strip() for g in generators_str.split(',')]

  relations = [
    r.strip()
    for r in relations_str.split(',')
    if r.strip()
  ]

  return generators, relations

def evaluate_relation(vertex, relation, generators):
  """
  Evaluate a relation starting from a vertex.

  Returns: True if relation holds at this vertex
  """
  current = vertex

  # Parse relation (e.g., "a^2", "ab", "(ab)^2")
  # Simplified: just concatenate generators
  for char in relation:
    if char in generators:
      gen_index = generators.index(char)
      current = multiply_by_generator(current, gen_index)

  return current == vertex  # Relation holds if we return to identity

Examples and Applications

Free groups

The Cayley graph of a free group ( F_n ) on ( n ) generators is an infinite ( 2n )-regular tree.

Vertices: Reduced words in generators
Edges: Word multiplication by a generator
Structure: Infinite binary tree (for ( n = 1 )), infinite ( 2n )-ary tree (for ( n > 1 ))

Cyclic groups

( \mathbb_n ) with generator ( {1} ):

Vertices: ( n ) vertices labeled ( 0, 1, \ldots, n-1 )
Edges: ( i \rightarrow i+1 \mod n ) (outgoing) and ( i \rightarrow i-1 \mod n ) (incoming)
Structure: Cycle graph ( C_n )

Dihedral groups

( D_n ) (symmetries of regular ( n )-gon) with generators ( {r, s} ) (rotation and reflection):

Vertices: ( 2n ) elements (n rotations + n reflections)
Edges: Rotation edges form a cycle, reflection edges connect opposite vertices
Structure: Regular polygon with antipodal connections

Coxeter groups

Coxeter groups have special Cayley graphs called Coxeter diagrams or Cayley complexes.

Generators: Simple reflections ( s_1, \ldots, s_n )
Relations: ( s*i^2 = e ), ( (s_i s_j)^ = e )
Structure: Cells correspond to parabolic subgroups

Applications

Group theory research: Visualize group structure, detect subgroups, study word problems
Chemistry: Visualize molecular symmetries and reaction pathways
Cryptography: Study group-based cryptography (e.g., braid group cryptography)
Network topology: Cayley graphs as network topologies for interconnects
Computer graphics: Symmetry detection and procedural generation

Interactive Exploration

Group exploration tool

Build an interactive tool to explore Cayley graphs of various groups.

// Interactive Cayley graph explorer
class CayleyGraphExplorer {
  constructor() {
    this.group = null;
    this.generators = [];
    this.graph = null;
    this.visualization = null;
  }

  async loadGroup(groupType, params) {
    switch (groupType) {
      case "symmetric":
        this.group = new SymmetricGroup(params.n);
        this.generators = this.group.standardGenerators();
        break;
      case "cyclic":
        this.group = new CyclicGroup(params.n);
        this.generators = [1];
        break;
      case "dihedral":
        this.group = new DihedralGroup(params.n);
        this.generators = this.group.standardGenerators();
        break;
    }

    this.graph = this.buildCayleyGraph();
  }

  buildCayleyGraph() {
    const graph = new DirectedGraph();

    this.group.elements.forEach((element) => {
      graph.addVertex(element);
    });

    this.group.elements.forEach((source) => {
      this.generators.forEach((generator, genIndex) => {
        const target = this.group.multiply(source, generator);
        graph.addEdge(source, target, {
          label: this.generators[genIndex],
          generator: genIndex,
        });
      });
    });

    return graph;
  }

  visualize(mode = "2d") {
    if (mode === "2d") {
      this.visualization = new ForceDirectedVisualization(this.graph);
    } else if (mode === "3d") {
      this.visualization = new ThreeJSVisualization(this.graph);
    } else if (mode === "xr") {
      this.visualization = new WebXRVisualization(this.graph);
    }

    this.visualization.render();
  }

  animateWord(word) {
    // Animate traversal of a word in the group
    let current = this.group.identity;

    word.forEach((generator, i) => {
      const next = this.group.multiply(current, generator);

      this.visualization.animateTransition(
        current,
        next,
        generator,
        i * 1000, // 1 second per step
      );

      current = next;
    });
  }
}

Subgroup highlighting

Visualize how subgroups appear within the Cayley graph.

function highlightSubgroup(graph, subgroup) {
  // Color vertices in subgroup
  subgroup.elements.forEach((element) => {
    const vertex = graph.findVertex(element);
    vertex.material = new THREE.MeshPhongMaterial({ color: 0xff4444 });
  });

  // Draw spanning subgraph
  subgroup.generators.forEach((generator, genIndex) => {
    subgroup.elements.forEach((source) => {
      const target = subgroup.multiply(source, generator);

      const edge = graph.findEdge(source, target, generator);
      edge.material = new THREE.MeshPhongMaterial({
        color: 0xff0000,
        emissive: 0xff0000,
        emissiveIntensity: 0.3,
      });
    });
  });
}

Cart

Wishlist

Your wishlist is empty

Formal Definition

Components

Notation

Properties

Example: Symmetric Group S₃

Group elements (6 total)

Generating set

Cayley graph construction

Visualization Approaches

2D Planar Embeddings

Force-directed layout

Spectral layout (Laplacian eigenvectors)

3D Spatial Visualizations

Three.js visualization

WebXR immersive visualization

Animation: Group Multiplication

Algorithmic Construction

Finite groups

Infinite groups (finitely generated)

Bounded region visualization

Group presentation parsing

Examples and Applications

Free groups

Cyclic groups

Dihedral groups

Coxeter groups

Applications

Interactive Exploration

Group exploration tool

Subgroup highlighting

Further Reading

Never miss a deep-dive

Formal Definition

Components

Notation

Properties

Example: Symmetric Group S₃

Group elements (6 total)

Generating set

Cayley graph construction

Visualization Approaches

2D Planar Embeddings

Force-directed layout

Spectral layout (Laplacian eigenvectors)

3D Spatial Visualizations

Three.js visualization

WebXR immersive visualization

Animation: Group Multiplication

Algorithmic Construction

Finite groups

Infinite groups (finitely generated)

Bounded region visualization

Group presentation parsing

Examples and Applications

Free groups

Cyclic groups

Dihedral groups

Coxeter groups

Applications

Interactive Exploration

Group exploration tool

Subgroup highlighting

Further Reading