Grafos mergulhados em superfícies orientáveis: emparelhamento e reconstrução

Abstract

In this work, we investigate graphs embedded in closed orientable surfaces from two complementary perspectives: edge pairings and embedding reconstruction. Regarding edge pairings, we implemented an algorithm that explicitly generates canonical embeddings on orientable surfaces. We show that for surfaces of genus 1, 2, 3, and 4, there exist exactly 1, 4, 82, and 7258 canonical pairings, respectively. Concerning the topological reconstruction of embeddings, we prove that every tree embedding is reconstructible, provided it does not contain degree-1 vertices attached to the center when the center is unique. Furthermore, in the study of cellular embedding reconstruction, we demonstrate that pairing graphs arising from the S1 surgery are reconstructible as embeddings, and we establish sufficient conditions to ensure the reconstructibility of cellular embeddings in general.