Improved bounds for guarding plane graphs with edges

DOI10.4230/LIPIcs.SWAT.2018.14zbMath1477.05052OpenAlexW2798106924MaRDI QIDQ5116478

Sander Verdonschot, Aurélien Ooms, Ahmad Biniaz, Prosenjit Bose

Publication date: 25 August 2020

Full work available at URL: https://dblp.uni-trier.de/db/conf/swat/swat2018.html#BiniazBOV18

zbMATH Keywords

graph coloringfour-color theoremedge guards

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Guarding polyhedral terrains
• Edge guarding polyhedral terrains
• Galleries need fewer mobile guards: A variation on Chvatal's theorem
• A short proof of Chvatal's Watchman Theorem
• Structure of neighborhoods of edges in planar graphs and simultaneous coloring of vertices, edges and faces
• A combinatorial theorem in plane geometry
• Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces
• Every Planar Map is Four Colorable

This page was built for publication: Improved bounds for guarding plane graphs with edges