Visibility Graph Recognition

Definitions and mathematical statement

The input is a finite simple graph $G$ on labelled vertices $1,\ldots,n$, together with a specified Hamiltonian cycle $C=(v_1,\ldots,v_n,v_1)$ in $G$. A realization consists of distinct points $p_1,\ldots,p_n\in\mathbb R^2$ such that the segments following $C$ form the boundary of a simple polygon $P$.

Two polygon vertices are visible when the entire closed segment between them lies in $P$, including its boundary. Require the exact equivalence \[ ij\in E(G)\quad\Longleftrightarrow\quad[p_i,p_j]\subset P \qquad(i\ne j). \] Thus every edge and every nonedge constrains the realization; merely drawing all graph edges inside some polygon is insufficient.

Can existence of such a realization be decided in time polynomial in the size of the graph input? More generally, determine the complexity of this recognition problem. The cycle supplies the intended boundary order in advance, but no coordinates. The polygon has no holes, and no extra vertices may be inserted. The decision problem does not automatically require a rational-coordinate witness of polynomial bit length; that would be a separate and stronger certificate claim.

Short English statement

Given a graph and its proposed polygon boundary cycle, decide whether the graph records exactly which pairs of vertices can see one another inside a simple polygon.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 5500017 (AMR-054-0017), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problems Project - Computational Geometry, Problem 17. Original source indexed by AMR-054-0017. https://topp.openproblem.net/p17.
• S3 Schaefer, Cardinal and Miltzow, The Existential Theory of the Reals as a Complexity Class: A Compendium, polygon visibility recognition. https://arxiv.org/abs/2407.18006.