A P-Completeness Result for Visibility Graphs of Simple Polygons

DOI10.1002/1521-3870(200008)46:3%3C361::AID-MALQ361%3E3.0.CO;2-0MaRDI QIDQ4511548zbMATH OpenOpenAlexFDO

Authors Jana Dietel, Hans-Dietrich Hecker

Publication date 30 October 2000

Full work available at URL https://doi.org/10.1002/1521-3870(200008)46:3%3C361::aid-malq361%3E3.0.co;2-0

zbMATH Keywords

P-completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 434872
• A note on the combinatorial structure of the visibility graph in simple polygons
• On the number of visibility graphs of simple polygons
• A new necessary condition for the vertex visibility graphs of simple polygons
• A characterization of visibility graphs for pseudo-polygons
• scientific article; zbMATH DE number 4085050
• On recognizing and characterizing visibility graphs of simple polygons
• On colourability of polygon visibility graphs
• A note on rectilinear and polar visibility graphs
• An optimal visibility graph algorithm for triangulated simple polygons

Cited in

(1)

• Visibility graphs of staircase polygons and the weak Bruhat order. I: From visibility graphs to maximal chains

This page was built for publication: A P-Completeness Result for Visibility Graphs of Simple Polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4511548)