Pentagon contact representation algorithm termination
Algorithm Termination Conjecture · arXiv:2004.05942
Status open high confidence
The conjecture that the algorithm for computing homothetic pentagon contact representations always terminates remains open as of 2026. No follow-up paper resolving or making partial progress on the termination question was found in the indexed literature. The analogous algorithms for homothetic triangle and square contact representations likewise lack termination proofs, suggesting this is a structurally difficult problem across the family.
Reviewer notes. No follow-up found. Searches returned only the original paper and its published version in Electronic Journal of Combinatorics (v25i3p39). DBLP page for Schrezenmaier shows no subsequent work on pentagon contact representations or algorithm termination. Semantic Scholar API returned no citing papers.
Context
The paper proposes an algorithm for computing homothetic pentagon contact representations based on systems of linear equations derived from five color forests. When the solution is non-negative it encodes distances between pentagon corners and the representation is constructed; otherwise negative variables guide a local change of the five color forest and the procedure restarts. The authors note that a proof of this conjecture would yield an existence proof for pentagon contact representations independent of Schramm's Monster Packing Theorem. Analogous algorithms for homothetic triangle and square contact representations exist but also lack termination proofs.
Notes. Stated in running prose in the introduction without a labelled theorem environment. PDF extraction quality is adequate for this prose statement.
Source paper
Pentagon contact representations
Stefan Felsner, Hendrik Schrezenmaier, Raphael Steiner · 2020-04-13
https://arxiv.org/abs/2004.05942
PDF source