Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces

DOI10.1016/S0925-7721(03)00027-0zbMath1022.05078OpenAlexW2061541114MaRDI QIDQ1410592

Zaiqing Li, David G. Kirkpatrick, Prosenjit Bose

Publication date: 14 October 2003

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0925-7721(03)00027-0

zbMATH Keywords

covercoloringplane graphfaceslinear-time algorithm

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) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (20)

Edge guards for polyhedra in three-space ⋮ Polychromatic colorings of hypergraphs with high balance ⋮ Facially-constrained colorings of plane graphs: a survey ⋮ Drawing Planar Graphs with Few Geometric Primitives ⋮ Computational complexity for the problem of optimal intersection of straight line segments by disks ⋮ Guarding a set of line segments in the plane ⋮ Approximation algorithms for a geometric set cover problem ⋮ Polychromatic colorings of plane graphs ⋮ Improved bounds for guarding plane graphs with edges ⋮ Box-respecting colorings of \(n\)-dimensional guillotine-partitions ⋮ Polychromatic 4-coloring of guillotine subdivisions ⋮ Experimental Study on Approximation Algorithms for Guarding Sets of Line Segments ⋮ A note on the lower bound of edge guards of polyhedral terrains ⋮ Polychromatic colorings of bounded degree plane graphs ⋮ Balanced polychromatic 2-coloring of triangulations ⋮ GUARDING RECTANGULAR PARTITIONS ⋮ Polychromatic colorings of rectangular partitions ⋮ Polychromatic colorings of arbitrary rectangular partitions ⋮ Improved bounds for guarding plane graphs with edges ⋮ A note on polychromatic colorings of plane graphs

Cites Work

• Guarding polyhedral terrains
• Edge guarding polyhedral terrains
• A short proof of Chvatal's Watchman Theorem
• Every planar map is four colorable. I: Discharging
• The four-colour theorem
• A combinatorial theorem in plane geometry
• Efficient Algorithms for Petersen's Matching Theorem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces