The Open Problems Project

Next: Problem 18: Pushing Disks Together

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.