next up previous
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 ``pseudo-polygon'' visibility graphs [OS97].
Appearances
[MO01]
Categories
visibility
Entry Revision History
J. O'Rourke, 2 Aug. 2001.

Bibliography

MO01
J. S. B. Mitchell and Joseph O'Rourke.
Computational geometry column 42.
Internat. J. Comput. Geom. Appl., 11(5):573-582, 2001.
Also in SIGACT News 32(3):63-72 (2001), Issue 120.

O'R93
Joseph O'Rourke.
Computational geometry column 18.
Internat. J. Comput. Geom. Appl., 3(1):107-113, 1993.
Also in SIGACT News 24:1 (1993), 20-25.

OS97
Joseph O'Rourke and Ileana Streinu.
Vertex-edge pseudo-visibility graphs: Characterization and recognition.
In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 119-128, 1997.



The Open Problems Project - December 04, 2015