Improved bounds for guarding plane graphs with edges

DOI10.4230/LIPICS.SWAT.2018.14MaRDI QIDQ5116478zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• Improved bounds for guarding plane graphs with edges
• Edge guarding polyhedral terrains
• Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces
• Edge guards in rectilinear polygons
• On the number of guard edges of a polygon

Cites work

• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 1391661 (Why is no real title available?)
• scientific article; zbMATH DE number 6776481 (Why is no real title available?)
• A combinatorial theorem in plane geometry
• A short proof of Chvatal's Watchman Theorem
• Edge guarding polyhedral terrains
• Every Planar Map is Four Colorable
• Galleries need fewer mobile guards: A variation on Chvatal's theorem
• Guarding polyhedral terrains
• Structure of neighborhoods of edges in planar graphs and simultaneous coloring of vertices, edges and faces
• Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces

Cited in

(2)

• Improved bounds for guarding plane graphs with edges
• Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces

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

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