Invariants of almost embeddings of graphs in the plane

Here is an explanation of the paper "Invariants of Almost Embeddings of Graphs in the Plane," translated into simple, everyday language with creative analogies.

The Big Picture: Drawing Graphs Without (Too Many) Crashes

Imagine you are an architect trying to draw a map of a city on a flat piece of paper. The "cities" are graphs (dots connected by lines), and the "paper" is the 2D plane.

Usually, mathematicians ask: "Can I draw this city so that no two roads cross each other?" If the answer is yes, the graph is planar. Famous examples of cities that cannot be drawn without crossing roads are $K_5$ (5 cities, all connected to each other) and $K_{3,3}$ (two groups of 3 cities, where everyone in one group is connected to everyone in the other).

But what if we relax the rules? What if we allow the roads to cross, but only if they don't cross at the wrong places?

This is the concept of an "Almost Embedding."

The Rule: Two roads (edges) can cross each other, unless they are "neighbors" (connected to the same city).
The Forbidden Move: A road cannot cross a city (vertex) that isn't one of its endpoints.
The Goal: We want to understand the "geometry of the mess." Even if the roads cross, is there a hidden mathematical order to how they cross?

The authors of this paper are like detectives trying to find the "fingerprints" of these messy drawings. They discovered specific numbers (called invariants) that describe the twisting and turning of the roads.

The Main Characters: The "Twist Counters"

The paper introduces three main ways to count how "knotted" or "twisted" a drawing is. Think of these as different ways to measure the chaos.

1. The Winding Number (The "Spin Counter")

Imagine you are standing at a specific city (a vertex). You look at a loop of roads that goes around you but doesn't touch you.

The Question: How many times does that loop spin around you?
The Analogy: Imagine a hula hoop spinning around your waist. If it spins once clockwise, the number is +1. If it spins counter-clockwise, it's -1. If it wiggles back and forth without completing a full circle, the number is 0.
The Discovery: For certain messy graphs (like $K_4$ , a tetrahedron shape), the authors found that if you add up these spin numbers for all the loops, the total must be an odd number. It can't be even. It's a strict rule of the universe for these drawings.

2. The Cyclic Number (The "Triangle Dance")

Imagine three roads forming a triangle.

The Question: If you trace the path of the three roads, how do they twist around each other?
The Analogy: Think of three dancers holding hands in a circle. If they spin around each other in a specific way, they create a "cyclic" pattern. The authors found that this pattern always results in an odd number of twists.
Why it matters: This helps prove that certain graphs simply cannot be drawn without violating the "almost embedding" rules.

3. The Triod Number (The "Y-Shape Twist")

Imagine a "Y" shape (three roads meeting at a central point).

The Question: How do the three arms of the "Y" twist around the center?
The Analogy: Think of a three-pronged fork spinning in a bowl of soup. The "Triod Number" measures how the soup swirls around the prongs.
The Discovery: Just like the other numbers, this twist count is always odd.

The "Magic" of the Math

The paper is full of "Theorems," which are like unbreakable laws of physics for these drawings.

The "Oddness" Law:
The most surprising finding is that for these specific "almost" drawings, the total twist count is always odd.

Analogy: Imagine you are trying to tie a knot in a string. If you try to make the knot "even" (symmetrical in a specific way), the universe says, "Nope, that's impossible." The knot must have a twist.
Why is this cool? It connects a simple drawing on a piece of paper to deep, abstract math (like the Borsuk-Ulam theorem, which is about how you can't comb a hairy ball flat without a cowlick).

The "Freedom" of the Mess:
The authors also showed that while there are rules (the numbers must be odd), you have a lot of freedom within those rules.

Analogy: Imagine you are building a tower of blocks. The rule is "The tower must be 5 blocks high." You can arrange the blocks however you want (red on blue, blue on red), as long as the height is 5.
The paper proves that for the graph $K_4$ , you can create almost any "odd" twist number you want. You can make the roads spin around a city 1 time, 3 times, 101 times, or -50 times. The only limit is that it must be an odd number.

The Deeper Connection: The "Deleted Square"

The authors use a fancy tool called the "Deleted Square" (or "Cut-out Square").

The Analogy: Imagine you have a giant square piece of paper representing all possible pairs of points on your graph. Now, you cut out the diagonal line where a point would be paired with itself (since a point can't be two places at once).
What's left is a weird, twisted shape. The authors realized that the "twist numbers" we discussed earlier are actually just counting how many times a path winds around the holes in this cut-out shape.
This connects the messy drawing on the floor to the clean geometry of a high-dimensional shape.

Why Should You Care?

You might think, "Who cares about drawing messy graphs?"

Computer Science: When designing computer chips or circuit boards, wires often cross. Understanding the "topology" (the shape) of these crossings helps engineers avoid short circuits or design better layouts.
Robotics: If you have a robot arm with multiple joints moving in a room, you need to know if the arm can move from point A to point B without hitting itself. This math helps calculate those "collision-free" paths.
Pure Curiosity: It shows that even in a "messy" situation (where things cross), there is a hidden, rigid order (the odd numbers). It's like finding a perfect rhythm in a chaotic jazz solo.

Summary in One Sentence

This paper proves that even when you draw a graph with messy, crossing lines (as long as you follow a few simple rules), the way those lines twist around each other follows a strict mathematical law: the total twist is always an odd number.

Here is a detailed technical summary of the paper "Invariants of Almost Embeddings of Graphs in the Plane" by E. Alkin, A. Miroshnikov, and A. Skopenkov.

1. Problem Statement

The paper addresses the classification and characterization of almost embeddings of graphs into the plane ( $\mathbb{R}^2$ ).

Definition: An almost embedding of a graph $K$ is a piecewise-linear (PL) map $f: K \to \mathbb{R}^2$ such that the images of any two non-adjacent simplices (vertices or edges) are disjoint. Unlike standard embeddings, adjacent edges are allowed to intersect (though the definition usually implies general position where intersections are transverse), and vertices must not lie on non-incident edges.
Context: While the non-existence of almost embeddings for non-planar graphs like $K_5$ and $K_{3,3}$ is a classical result (Hanani-Tutte, van Kampen-Flores theorems), the paper focuses on graphs that do admit almost embeddings (e.g., $K_4$ , $K_5$ minus an edge, $K_{3,3}$ minus an edge).
Goal: To define, compute, and relate integer-valued invariants (winding numbers, cyclic numbers, triod numbers, and Wu numbers) for these almost embeddings. The authors aim to describe the set of all possible values these invariants can take and determine if these invariants classify almost embeddings up to almost isotopy.

2. Methodology

The authors employ a blend of combinatorial topology, algebraic topology, and geometric construction:

Geometric Definitions: They define invariants using winding numbers (rotation numbers) of closed polygonal chains around points. They introduce "finger moves" (local deformations) to construct specific examples realizing arbitrary integer values for certain invariants.
Algebraic Topology: The core theoretical framework relies on the deleted product (or deleted square) of a graph, denoted $\tilde{K} = \{(x,y) \in K \times K \mid x \neq y\}$ $\tilde{K} = {(x, y) \in K \times K ∣ x \neq = y}$ .
- They analyze the first homology group $H_1(\tilde{K}; \mathbb{Z})$ .
- They define Wu numbers (or Wu invariants) as homomorphisms from $H_1(\tilde{K}; \mathbb{Z})$ to $\mathbb{Z}$ , derived from the rotation of vectors between disjoint edges.
Theorems and Lemmas:
- Borsuk-Ulam Theorem: Used to prove parity constraints (oddness) for certain invariants.
- Radon's Theorem (Topological Version): Used to relate intersection numbers to winding numbers.
- Hanani-Tutte Theorem: Used as a baseline for non-embeddability and as a source for parity arguments in $K_5$ and $K_{3,3}$ .
Constructive Proofs: The paper provides explicit geometric constructions (using "finger moves" and subdivisions) to show that certain constraints are the only constraints on the invariants.

3. Key Contributions and Results

A. Definition of Invariants

The paper formalizes three primary integer invariants for almost embeddings:

Winding Numbers ( $w_f(C, v)$ ): The winding number of a cycle $C$ around a vertex $v$ not in $C$ .
Cyclic Numbers ( $cy_f$ ): A generalized winding number for a triple of paths forming a cycle (related to the degree of a map from a torus).
Triod Numbers ( $tr_f$ ): An invariant for a "triod" (three paths meeting at a central vertex), measuring the rotation of vectors between the endpoints.

B. Relations Between Invariants

The authors establish deep algebraic relations between these invariants:

For $K_4$ :
- Theorem 4.2: For any almost embedding of $K_4$ , the alternating sum of winding numbers $W_f = \sum (-1)^j w_f(j)$ is odd.
- Theorem 4.3: Conversely, for any set of integers $n_1, n_2, n_3, n_4$ such that their alternating sum is odd, there exists an almost embedding realizing these values. This completely solves the realization problem for $K_4$ .
- Relations: The paper proves that $2W_f = cy_f(1) - cy_f(2) + cy_f(3) - cy_f(4) $and expresses triod numbers directly in terms of$ W_f$.
For $K_5$ minus an edge ( $K_5 - e$ ):
- Theorem 5.3: The difference of winding numbers for the two vertices of the missing edge is odd.
- Theorem 5.3(b) (New Result): This difference is not just odd, but specifically $\pm 1$ . This is a non-trivial geometric result (proven by T. Garaev) that does not follow from Borsuk-Ulam alone.
For $K_{3,3}$ minus an edge:
- Similar parity constraints are derived, and the realization of values is shown to be unconstrained except for the parity condition (Theorem 5.6, Example 5.7).

C. Generalization to Wu Numbers

The authors generalize these invariants to Wu numbers parameterized by elements of the homology group $H_1(\tilde{K}; \mathbb{Z})$ .

Theorem 9.6 & 9.7: Any Wu number for a graph $K$ (specifically for polyhedral graphs or connected graphs) can be expressed as a rational linear combination of winding, cyclic, and triod numbers. This reduces the study of general homological invariants to the study of the three basic types.

D. Classification and Open Problems

Classification: The paper discusses whether these invariants classify almost embeddings up to almost isotopy (continuous deformation preserving the almost embedding property).
- For standard embeddings, cyclic and triod numbers classify the embedding (Theorem 10.1).
- For almost embeddings, the authors conjecture (Hypothesis 10.3) that triod numbers might classify almost embeddings of trees, but note that for general graphs, the invariants are not sufficient to distinguish all almost isotopy classes.
Open Problems:
- Problem 6.1 / 9.5: A complete description of the set of all realizable tuples of invariants for general graphs (e.g., $K_5 - e$ ) remains open, though partial solutions are provided.
- Hypothesis 6.3: A specific conjecture regarding the realizability of winding numbers for $K_5 - e$ .

4. Significance

Bridging Discrete and Continuous: The paper successfully bridges combinatorial graph theory (planarity, minors) with algebraic topology (homology of configuration spaces, Borsuk-Ulam).
Quantitative Refinement: It moves beyond qualitative "embeddable vs. non-embeddable" questions to quantitative questions: "How many times do edges wind around each other?" and "What integer values are possible?"
New Theorems: The result that the difference of winding numbers for $K_5 - e$ is exactly $\pm 1$ (Theorem 5.3b) is a significant new contribution, distinguishing almost embeddings from general maps where the value could be any odd integer.
Educational Value: The paper is structured as a review, making advanced topological concepts (deleted products, Wu invariants) accessible to students and computer scientists by using elementary geometric examples and "finger moves" before introducing heavy machinery.
Algorithmic Implications: The discussion touches on the algorithmic complexity of recognizing almost embeddings, linking it to the NP-hardness of embedding simplicial complexes in higher dimensions.

In summary, this paper provides a comprehensive framework for understanding the topological obstructions to embedding graphs in the plane, characterizing the precise integer invariants that arise when "almost" embeddings are considered, and establishing the limits of these invariants in classifying such structures.