OP-00834 Solution claimed

Spanning triangulated spheres with holes in surface triangulations

Let $\mathbb{S}_g$ be the sphere with $g$ open disks removed, the closures of the disks being pairwise disjoint. A triangulation of a compact surface is an embedding of a finite simple graph that contains the boundary of the surface and in which every face is an open disk bounded by a triangle of the graph. The Euler genus of the closed orientable surface with $h$ handles is $2h$, and that of the closed nonorientable surface with $h$ crosscaps is $h$. Clinch, Dewar, Fuladi, Gorsky, Huynh, Kastis, Nakamoto, Nixon and Servatius record that every triangulation of the projective plane contains a spanning triangulated disk (Nakamoto and Nozawa; Nevo and Tarabykin) and every triangulation of the torus a spanning triangulated cylinder (Nevo and Tarabykin; the paper gives a new short proof), and prove that a triangulation of the orientable surface with $h$ handles and facewidth at least $\gamma(h)$ contains a spanning triangulated $\mathbb{S}_{2h}$. They also show that for every $g > g' \ge 0$ there are triangulations of Euler genus $g$ and arbitrarily large facewidth with no spanning triangulated $\mathbb{S}_{g'}$.

Problem. Is it true that every triangulation $G$ of every closed connected surface of Euler genus $g$ contains a spanning subgraph that is a triangulation of $\mathbb{S}_g$? Spanning means that all vertices of $G$ are kept; no new vertices may be added.

Source: Clinch, Dewar, Fuladi, Gorsky, Huynh, Kastis, Nakamoto, Nixon and Servatius (2026), Conjecture 1.3, strengthening a conjecture of Nevo and Tarabykin on spanning planar Laman subgraphs.

Imported from github.com/MColbrook/AIM.

Classification

Primary: CO — Combinatorics
Secondary: GT
Keywords: AIM Open Applied Problems, spanning subgraphs, surface triangulations, triangulated spheres with holes

References

@article{clinch2026,
  author        = {Clinch, Katie and Dewar, Sean and Fuladi, Niloufar and Gorsky, Maximilian and Huynh, Tony and Kastis, Eleftherios and Nakamoto, Atsuhiro and Nixon, Anthony and Servatius, Brigitte},
  title         = {Triangulated Spheres with Holes in Triangulated Surfaces},
  journal       = {Discrete Comput. Geom.},
  volume        = {76},
  number        = {3},
  year          = {2026},
  pages         = {1537--1546},
  doi           = {10.1007/s00454-026-00836-8},
  eprint        = {2410.04450},
  archivePrefix = {arXiv},
}
@misc{aim-spanning-holed-sphere-triangulation,
  author       = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
  title        = {{Spanning triangulated spheres with holes in surface triangulations}},
  howpublished = {AIM --- Open Applied Problems, GitHub repository},
  year         = {2026},
  url          = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/619-spanning-holed-sphere-triangulation.md},
  note         = {Entry 619 at commit 24edaad, 2026-10-15},
}

Resolution claims

Polyhedra of genus 2 with 10 vertices and minimal coordinates v1 arXiv ↗

Stefan Hougardy; Frank H. Lutz; Mariano Zelke

We give coordinate-minimal geometric realizations in general position of all 865 vertex-minimal triangulations of the orientable surface of genus 2 in the 4x4x4-cube.

Counterexample · not verified · fidelity not established · posted on arXiv 28 Jul 2005

Status history

When	Change	By	Reason
2026-10-21	Needs verification → Solution claimed	—	Recorded here: arXiv:math/0507592v1.

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00834, "Spanning triangulated spheres with holes in surface triangulations", clopen.solutions.