Next: Problem 18: Pushing Disks
Up: The Open Problems Project
Previous: Problem 16: Simple Polygonalizations
Problem 17: Visibility Graph Recognition
 Statement
 Given a visibility graph G and a Hamiltonian circuit C,
determine in polynomial time whether there is a simple polygon whose
vertex visibility graph is G, and whose boundary corresponds to C.
 Origin
 ElGindy(?)
 Status/Conjectures
 Open.
 Partial and Related Results
 The problem is not even known to be in NP [O'R93],
although it is
for ``pseudopolygon'' visibility
graphs [OS97].
 Appearances
 [MO01]
 Categories
 visibility
 Entry Revision History
 J. O'Rourke, 2 Aug. 2001.
 MO01

J. S. B. Mitchell and Joseph O'Rourke.
Computational geometry column 42.
Internat. J. Comput. Geom. Appl., 11(5):573582, 2001.
Also in SIGACT News 32(3):6372 (2001), Issue 120.
 O'R93

Joseph O'Rourke.
Computational geometry column 18.
Internat. J. Comput. Geom. Appl., 3(1):107113, 1993.
Also in SIGACT News 24:1 (1993), 2025.
 OS97

Joseph O'Rourke and Ileana Streinu.
Vertexedge pseudovisibility graphs: Characterization and
recognition.
In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 119128,
1997.
The Open Problems Project  September 19, 2017