[Combinatorial maps] Add exact faces, Euler characteristic, genus, orientation, and dual transforms

[morluto]

Summary

The research/conjecture audit repeatedly reaches embedded finite graphs, but the useful reusable object is not a planarity solver or a certificate checker. It is a well-formed finite combinatorial map—a graph with a cyclic order of darts around each vertex—from which ordinary exact functions derive faces, Euler characteristic, genus, orientation reversal, connected components, and a dual map.

The public boundary should therefore be:

well-formed finite combinatorial map
    -> exact face permutation and facial walks
    -> componentwise Euler characteristic and orientable genus
    -> orientation reversal
    -> exact dual combinatorial map

This is a direct structural mathematics layer. It deliberately excludes graph.planarity.decide, Kuratowski search, candidate verification, geometric drawing, and theorem-specific planar-graph APIs.

Audit baseline: main at 1495a5d803f28bb5cc679bf260ea83e33f65991c.

Why the value is the missing abstraction

A rotation system can be represented using stable directed-dart identity:

vertices: finite labelled domain
darts:
  dart_id
  tail
  head
  reverse_dart_id
rotation:
  for each vertex, one cyclic ordering of exactly its outgoing darts

For an ordinary simple undirected graph, each edge contributes two opposite darts. The same value also handles bridges correctly: a bridge's two darts may occur on the same facial boundary. A face is an orbit of the permutation obtained by composing dart reversal with the local rotation successor.

The request model should parse only well-formed maps:

• every dart has one declared tail/head;
• reverse is a fixed-point-free involution exchanging endpoints;
• every outgoing dart appears exactly once in the rotation at its tail;
• each rotation is a cyclic order, not an arbitrary list with repeated or foreign darts;
• labels and total incidences are finite and bounded.

These are value-construction invariants. They should not become a public .check operation.

Domain-owned values

FiniteCombinatorialMap

An immutable dart/rotation value with explicit component and orientation convention.

FacialWalk

A cyclic dart sequence, canonicalized only for transport by a documented representative. Cyclic shifts denote the same face; an orientation reversal is not silently identified with the original oriented face.

EmbeddedDualMap

A combinatorial map whose vertices are primal faces and whose darts correspond one-for-one with primal darts. The value must support loops and parallel edges; do not squeeze the dual into SimpleUndirectedGraph.

Proposed atomic functions

combinatorial_map.faces.compute

Input: one bounded FiniteCombinatorialMap.

Output:

complete face-orbit family
face_of_dart map
dart-successor permutation
face lengths
per-component face partition

Every dart occurs in exactly one facial walk. The total number of retained dart occurrences is exactly the number of darts.

combinatorial_map.euler_characteristic.compute

Return per connected component and in total:

V
E = |darts|/2
F
chi = V-E+F

State the disconnected-surface convention explicitly. Do not use an outer-face convention that conflates disconnected plane drawings with disjoint closed surfaces.

combinatorial_map.orientable_genus.compute

For each connected component, compute exactly:

g = (2-chi)/2

under the orientable cellular-map convention, plus the total genus of the disjoint union. The result is an exact nonnegative integer for a valid orientable combinatorial map.

This function classifies the supplied embedding. It does not search for a minimum-genus embedding of the underlying graph.

combinatorial_map.orientation_reverse.compute

Reverse every local cyclic order and return the resulting combinatorial map together with the induced bijection on faces. Applying the operation twice returns the original map exactly under canonical transport conventions.

combinatorial_map.connected_components.compute

Return the component partition of vertices, darts, and faces. This is useful when downstream topology treats components independently.

combinatorial_map.dual.compute

Return the exact embedded dual:

• one dual vertex per primal face;
• one dual dart per primal dart;
• dual reversal inherited from primal reversal;
• dual tail/head determined by the two incident face sides;
• dual rotation determined by primal vertex incidence;
• explicit primal-dart ↔ dual-dart bijection.

The dual of a bridge becomes a loop. Parallel dual edges are retained with identity. This operation therefore depends on, or should introduce locally, a small dart-based multigraph value rather than weakening the current simple-graph contract.

combinatorial_map.vertex_face_incidence.compute

Return the exact finite incidence structure between primal vertices and faces, including multiplicity when one vertex occurs several times on a facial boundary. A simple Boolean incidence projection may be returned separately from the multiplicity table when both are useful.

Mathematical semantics and invariances

• Reordering vertex, dart, and rotation rows does not change the map.
• Cyclically rotating one local rotation does not change the map.
• Coherent vertex/dart relabelling transports all results equivariantly.
• Reversing every local rotation preserves V,E,F,chi,g and reverses facial orientation.
• Bridges and loops in the dual are represented through darts, not erased.
• Face starting darts are a serialization convention, not mathematical identity.
• dual(dual(M)) is canonically isomorphic to M; return the explicit dart/vertex correspondence needed to test that relation.
• Genus is the genus of the supplied cellular embedding, not graph genus.

Public bounds

Reject before orbit construction when any supported limit is exceeded:

• vertex count;
• dart/edge count;
• aggregate label bytes;
• maximum local rotation length;
• total rotation incidences;
• face-walk output rows;
• dual map rows;
• vertex-face incidence cells; and
• aggregate result bytes.

All proposed functions are deterministic and complete for accepted values. They need no UNKNOWN, timeout-as-mathematics, search budget, or solver outcome.

Implementation direction

Use a small exact permutation/orbit kernel over immutable IDs. NetworkX or Sage may be used as conformance or private conversion sources, but no backend embedding object crosses the boundary.

Keep the implementation as ordinary domain functions and concrete request/result models. Do not add:

• planarity or minimum-genus search;
• Kuratowski-witness production;
• coordinate drawing;
• a generic topology/certificate framework;
• mutable embedding sessions;
• artifact identity; or
• a graph-conjecture workflow.

Required fixtures

1. one isolated vertex;
2. a single edge, showing both darts on one facial boundary under the chosen closed-surface map convention;
3. a cycle embedded on the sphere;
4. a tree with repeated vertices/darts along its unique face boundary;
5. K4 in a spherical embedding;
6. a standard torus cellulation with genus one;
7. disconnected components with independent Euler/genus rows;
8. local cyclic-order rotations and global row permutations;
9. coherent relabelling;
10. global orientation reversal;
11. exact primal/dual dart bijection;
12. a primal bridge producing a dual loop;
13. parallel edges in the dual retained distinctly;
14. dual(dual(M)) round-trip correspondence;
15. vertex-face incidence multiplicities; and
16. requests exactly at and immediately above every vertex, dart, incidence, dual-output, and byte limit.

Benchmark leverage

Use pure compositional tasks such as:

rotation system -> faces -> Euler characteristic -> genus
rotation system -> dual -> dual degree/face profile
orientation reversal -> transformed face walks
map -> vertex-face incidence -> ordinary incidence operations

Benchmark mutations should relabel darts, cyclically rotate local orders, reverse orientation, or change one local rotation in a way that predictably changes faces/genus. Do not ask the benchmark to solve planarity or validate a candidate certificate.

Acceptance criteria

• A finite combinatorial map has one bounded immutable dart/rotation value.
• Faces are exact orbits of the published dart permutation and partition every dart once.
• Euler characteristic and orientable genus are exact derived integers for the supplied embedding.
• Orientation reversal and connected-component projections are pure deterministic transforms.
• The dual retains loops, parallel edges, and a complete primal/dual dart correspondence.
• Relabelling and cyclic-order transport obey the stated invariances.
• Every function has finite structural and output bounds and no search/solver semantics.
• No planarity decision, Kuratowski finder/checker, drawing subsystem, persistent map object, generic certificate algebra, or theorem wrapper is introduced.

Related

• [Graph theory] Add bounded finite-multigraph flow and cycle-multicover operations #1680 owns edge-identified multigraph values useful for the dual result.
• [Incidence structures] Add exact matrices, profiles, duals, complements, restrictions, and derived/residual transforms #1732 owns general finite incidence structures; vertex_face_incidence.compute should return its concrete value when conventions align.
• [Out of scope] Do not add planarity classification or certificate-checking endpoints to the function-only portfolio #1725 is superseded by this function-first scope and should not remain as a duplicate planarity solver issue.