Recognition and Complexity of Point Visibility Graphs

DOI10.4230/LIPICS.SOCG.2015.171MaRDI QIDQ5368684zbMATH OpenOpenAlexFDO

Authors Jean Cardinal, Udo Hoffmann

Publication date 10 October 2017

Full work available at URL https://doi.org/10.4230/LIPIcs.SOCG.2015.171

zbMATH Keywords

existential theory of the realspoint visibility graphsrecognition

Mathematics Subject Classification ID

Logic in computer science (03B70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Recognition and complexity of point visibility graphs
• Computational complexity aspects of point visibility graphs
• Point visibility graph recognition is NP-hard
• scientific article; zbMATH DE number 4085050
• On recognizing and characterizing visibility graphs of simple polygons
• COMPLEXITY ASPECTS OF VISIBILITY GRAPHS
• scientific article; zbMATH DE number 5542506
• Visibility graphs of point sets in the plane

Cited in

(6)

• Computational complexity aspects of point visibility graphs
• Point visibility graph recognition is NP-hard
• COMPLEXITY ASPECTS OF VISIBILITY GRAPHS
• Recognition and complexity of point visibility graphs
• Recognizing Visibility Graphs of Triangulated Irregular Networks
• Visibility graphs of point sets in the plane

This page was built for publication: Recognition and Complexity of Point Visibility Graphs

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