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.