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

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

Zaiqing Li, David G. Kirkpatrick, Prosenjit Bose

Publication date: 14 October 2003

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

zbMATH Keywords

cover; coloring; plane graph; faces; linear-time algorithm

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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