Improved bounds for guarding plane graphs with edges
From MaRDI portal
Publication:1741583
DOI10.1007/s00373-018-02004-zzbMath1409.05081arXiv1804.07150OpenAlexW2908868776MaRDI QIDQ1741583
Sander Verdonschot, Aurélien Ooms, Ahmad Biniaz, Prosenjit Bose
Publication date: 3 May 2019
Published in: Graphs and Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1804.07150
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
- Quelques consequences simples de la formule d'Euler
- Every Planar Map is Four Colorable