Duality and minors for embeddings of graphs in pseudosurfaces
Abstract
Cellular embeddings of graphs in surfaces have well-defined duality and minor (edge contraction and deletion) operations that interact in a natural way. A pseudosurface is obtained from a surface (compact 2-manifold) by a finite number of identifications of finite sets of points. Points that are created by the identifications do not have a neighborhood homeomorphic to an open disk and are known as pinchpoints. Embeddings of graphs in pseudosurfaces have been considered, both implicitly and explicitly, since the 1960s. Usually the condition that all pinchpoints correspond to vertices of the graph is imposed. However, this makes it difficult to define duality and minors for pseudosurface embeddings and have these operations interact in the expected way. We define the class of pseudocellular embeddings of graphs in pseudosurfaces, which allow pinchpoints at places other than vertices, in particular in the middle of faces or edges. A subclass known as quasicellular embeddings corresponds to previous embedding models due to Deneen, Shute, and Thomborson and to Huggett and Moffatt. Pseudocellular embeddings also generalize other structures, including the edge-point ribbon graphs of Ellis-Monaghan, Kauffman, and Moffatt, and cyclically ordered graphs or cogs (also known as rigid-vertex graphs). Duality and minor operations for pseudocellular embeddings have very simple and straightforward definitions using topological quotient operations. Pseudocellular embeddings of edgeless graphs have nontrivial structure, and we define some minor operations for those that are related to `t-minor' operations on bipartite graphs. We develop a family of polynomial invariants for pseudocellular embeddings and discuss connections to other polynomial invariants.
Related
- Strong isometric path complexity of graphs: Asymptotic minors, restricted holes, and graph operations
- Positive Lin-Lu-Yau curvature, planar graphs, and forbidden minors
- T-embeddings as stationary measures on T-graphs
- Exact-palette rainbow embeddings in uniformly coloured pseudorandom graphs
- Induced Embeddings of Graphs into Abelian Cayley Graphs
BibTeX
@misc{dunshee2026duality,
title = {{Duality and minors for embeddings of graphs in pseudosurfaces}},
author = {Blake Dunshee and M. N. Ellingham and Joanna A. Ellis-Monaghan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.22061},
eprint = {2609.22061},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.22061},
}
RIS
TY - UNPB
TI - Duality and minors for embeddings of graphs in pseudosurfaces
AU - Blake Dunshee
AU - M. N. Ellingham
AU - Joanna A. Ellis-Monaghan
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.22061
UR - https://arxiv.org/abs/2609.22061
AB - Cellular embeddings of graphs in surfaces have well-defined duality and minor (edge contraction and deletion) operations that interact in a natural way. A pseudosurface is obtained from a surface (compact 2-manifold) by a finite number of identifications of finite sets of points. Points that are created by the identifications do not have a neighborhood homeomorphic to an open disk and are known as pinchpoints. Embeddings of graphs in pseudosurfaces have been considered, both implicitly and explicitly, since the 1960s. Usually the condition that all pinchpoints correspond to vertices of the graph is imposed. However, this makes it difficult to define duality and minors for pseudosurface embeddings and have these operations interact in the expected way. We define the class of pseudocellular embeddings of graphs in pseudosurfaces, which allow pinchpoints at places other than vertices, in particular in the middle of faces or edges. A subclass known as quasicellular embeddings corresponds to previous embedding models due to Deneen, Shute, and Thomborson and to Huggett and Moffatt. Pseudocellular embeddings also generalize other structures, including the edge-point ribbon graphs of Ellis-Monaghan, Kauffman, and Moffatt, and cyclically ordered graphs or cogs (also known as rigid-vertex graphs). Duality and minor operations for pseudocellular embeddings have very simple and straightforward definitions using topological quotient operations. Pseudocellular embeddings of edgeless graphs have nontrivial structure, and we define some minor operations for those that are related to `t-minor' operations on bipartite graphs. We develop a family of polynomial invariants for pseudocellular embeddings and discuss connections to other polynomial invariants.
ER -