Improved bounds for guarding plane graphs with edges

DOI10.4230/LIPICS.SWAT.2018.14zbMATH Open1477.05052OpenAlexW2798106924MaRDI QIDQ5116478FDOQ5116478

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

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

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

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

Cited In (1)

• 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)