The Kepler Conjecture 2025, 48 - Classification of Tame Plane Graphs

A partial plane graph is a graph, marked so that it's in a transitional state, so it will be used to generate further plane graphs. All its faces are marked as complete or incomplete. It's classification is determined according to the markings, requiring that no two incomplete faces share an edge. A patch is a partial plane graph P with 2 distinguished faces E, F, so that

• All vertices of P lie in E or F
• F is the only complete face
• E, F share an edge
• all vertices in F not in E have degree 2

E, F will be referred to as the distinguished incomplete and the distinguished complete faces, respectively. They modify partial plane graphs by cutting away faces and gluing the holes together at the boundary. All graphs are technically constructable this way, though it's often not the easiest way. Every terminal graph along that path violates one of the defining properties of tameness, or isomorphic terminal graphs can be reached by some other path not terminated early. These are done by pruning strategies. Pruning strategies of the first type include

• If the current state contains an incomplete face of length 3, eliminate all transitions except of the one carrying the partial plane graph to a partial plane graph that is the same except that the face has become complete.
• If the current state contains an incomplete face of length 4, eliminate all transitions except those leading to Prop. 3, so that each depicted face is interpreted as complete
• Remove all transitions with patches whose complete face has length > 8
• Often any admissible weight assignment will give total weight greater than tgt. In such cases, all transitions out of the partial plane graph can be pruned.

Of the second type,

• At a given state, fix one incomplete face and one of its edges, then follow only translations patching along that face and add a complete face along that edge
• In leading out from the initial state I_n, follow paths in which all added complete faces has length ≤ n.
• A list of all type (p, q) with b(p, q) < tgt, remove initial I₃, I₄, create new initial states I_p,q in the finite state machine. Define them to consist of p + q + 1 faces with p complete triangles, q complete quadrilaterals, meeting at a vertex. Choose a linear order.

If A, B are triangular or quadrilateral faces with at least 2 vertices in common in a tame graph, then the faces have exactly 2 vertices in common and an edge is shared.

Every tame plane graph is isomorphic to a plane graph mentioned above.