Dataset of Edmonds' bi-vectors and tri-vectors with realizations.

Area of Science:

• Graph theory
• Computational topology
• Discrete geometry

Background:

• Dual graphs and their relation to map embeddings were introduced by Jack Edmonds in 1965.
• A necessary condition for dual graphs G and G* relates their degree sequences (d, t) and the Euler characteristic of the surface.
• Characterizing which degree sequence pairs (bi-vectors) are realizable (geographic) remains an open problem.

Purpose of the Study:

• To extend the concept of geographic bi-vectors to geographic tri-vectors for 3-colored even multigraphs.
• To establish conditions for tri-vectors (d, t, δ) to be feasible and geographic.
• To present a dataset of geographic bi-vectors and tri-vectors with proofs of their geographic nature.

Main Methods:

• Definition of 3-colored even multigraphs embedded in a surface with triangular faces.
• Formulation of the feasibility condition for tri-vectors based on vertex color degrees and Euler characteristic.
• Construction and verification of realizations for geographic bi-vectors and tri-vectors.

Main Results:

• A necessary condition for dual graph embeddings involving degree sequences and Euler characteristic was recalled.
• The concept of feasible and geographic tri-vectors was formally defined for 3-colored triangulations.
• A dataset of geographic bi-vectors and tri-vectors, with supporting realizations, was compiled.

Conclusions:

• Geographic tri-vectors generalize geographic bi-vectors, offering a richer framework for studying surface embeddings.
• The presented dataset provides concrete examples and proofs for these graph structures.
• This work contributes to the open problem of characterizing realizable degree sequences in graph embeddings.