How to guard orthogonal polygons: diagonal graphs and vertex covers

DOI10.1007/s00454-015-9756-0zbMath1332.05057OpenAlexW2283810146MaRDI QIDQ262314

T. S. Michael, Val Pinciu

Publication date: 29 March 2016

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-015-9756-0

zbMATH Keywords

visibilityorthogonal polygonvertex coverart gallery theorem

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Other problems of combinatorial convexity (52A37) Polytopes and polyhedra (52B99)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An alternative proof of the rectilinear art gallery theorem
• Orthogonal art galleries with holes: a coloring proof of Aggarwal's theorem
• Approximation algorithms for art gallery problems in polygons
• A short proof of Chvatal's Watchman Theorem
• Art gallery theorems for guarded guards.
• On guarding the vertices of rectilinear domains
• Traditional Galleries Require Fewer Watchmen
• Finding Independent Sets in Triangle-Free Graphs
• Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
• A Graph-Coloring Result and Its Consequences for Polygon-Guarding Problems
• An exact algorithm for minimizing vertex guards on art galleries
• On Even Triangulations of 2-Connected Embedded Graphs

This page was built for publication: How to guard orthogonal polygons: diagonal graphs and vertex covers