Recognizing visibility graphs of simple polygons
The boundary of a simple polygon is a Hamiltonian cycle in the polygon's vertex visibility graph. The recognition problem asks to reverse this: from a graph together with a Hamiltonian cycle, decide whether some simple polygon realizes the pair.
O'Rourke observed that this decision problem is not even known to lie in NP. For pseudo-polygons, O'Rourke and Streinu characterized vertex-edge visibility graphs combinatorially, which places the recognition of their vertex visibility graphs in NP.
Problem. Given a graph $G$ and a Hamiltonian cycle $C$ of $G$, can one decide in polynomial time whether some simple polygon has vertex visibility graph $G$, with $C$ as its boundary?
Source: Origin uncertain, possibly ElGindy; Problem 17 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG
- Keywords
- simple polygon, The Open Problems Project, visibility graph recognition
References
@article{orourke1993,
author = {O'Rourke, Joseph},
title = {Computational geometry column 18},
journal = {Internat. J. Comput. Geom. Appl.},
volume = {3},
number = {1},
year = {1993},
pages = {107--113},
}
@inproceedings{orourkestreinu1997,
author = {O'Rourke, Joseph and Streinu, Ileana},
title = {Vertex-edge pseudo-visibility graphs: characterization and recognition},
booktitle = {Proc. 13th Annu. ACM Sympos. Comput. Geom.},
year = {1997},
pages = {119--128},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01074, "Recognizing visibility graphs of simple polygons", clopen.solutions.