Document Open Access Logo

Improved Bounds for Guarding Plane Graphs with Edges

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.SWAT.2018.14.pdf
  • Filesize: 0.76 MB
  • 12 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Mathematics of computing → Graph theory
Keywords
  • edge guards
  • graph coloring
  • four-color theorem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

An edge guard set of a plane graph G is a subset Gamma of edges of G such that each face of G is incident to an endpoint of an edge in Gamma. Such a set is said to guard G. We improve the known upper bounds on the number of edges required to guard any n-vertex embedded planar graph G:
1) We present a simple inductive proof for a theorem of Everett and Rivera-Campo (1997) that G can be guarded with at most 2n/5 edges, then extend this approach with a deeper analysis to yield an improved bound of 3n/8 edges for any plane graph.
2) We prove that there exists an edge guard set of G with at most n/(3) + alpha/9 edges, where alpha is the number of quadrilateral faces in G. This improves the previous bound of n/(3) + alpha by Bose, Kirkpatrick, and Li (2003). Moreover, if there is no short path between any two quadrilateral faces in G, we show that n/(3) edges suffice, removing the dependence on alpha.

Cite As Get BibTex

Ahmad Biniaz, Prosenjit Bose, Aurélien Ooms, and Sander Verdonschot. Improved Bounds for Guarding Plane Graphs with Edges. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SWAT.2018.14

Author Details

Ahmad Biniaz
  • Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada
Prosenjit Bose
  • School of Computer Science, Carleton University, Ottawa, Canada
Aurélien Ooms
  • Département d'Informatique, Université libre de Bruxelles (ULB), Brussels, Belgium
Sander Verdonschot
  • School of Computer Science, Carleton University, Ottawa, Canada

Funding

  • Biniaz, Ahmad: Supported by NSERC and Fields postdoctoral fellowships.
  • Bose, Prosenjit: Supported by NSERC.
  • Ooms, Aurélien: Supported by the Fund for Research Training in Industry and Agriculture (FRIA).
  • Verdonschot, Sander: Partially supported by NSERC and the Carleton-Fields Postdoctoral Award.

References

  1. Kenneth Appel and Wolfgang Haken. Every planar map is four colorable, volume 98 of Contemporary Mathematics. American Mathematical Society, Providence, RI, 1989. With the collaboration of J. Koch. URL: http://dx.doi.org/10.1090/conm/098.
  2. Oleg V. Borodin. Structure of neighborhoods of an edge in planar graphs and the simultaneous coloring of vertices, edges, and faces. Matematicheskie Zametki, 53(5):35-47, 1993. Google Scholar
  3. Prosenjit Bose, David G. Kirkpatrick, and Zaiqing Li. Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces. Computational Geometry: Theory and Applications, 26(3):209-219, 2003. Google Scholar
  4. Prosenjit Bose, Thomas C. Shermer, Godfried T. Toussaint, and Binhai Zhu. Guarding polyhedral terrains. Computational Geometry: Theory and Applications, 7:173-185, 1997. Google Scholar
  5. Václav Chvátal. A combinatorial theorem in plane geometry. Journal of Combinatorial Theory, Series B, 18:39-41, 1975. Google Scholar
  6. Hazel Everett and Eduardo Rivera-Campo. Edge guarding polyhedral terrains. Computational Geometry: Theory and Applications, 7:201-203, 1997. Google Scholar
  7. Steve Fisk. A short proof of Chvatal’s watchman theorem. Journal of Combinatorial Theory, Series B, 24(3):374, 1978. Google Scholar
  8. Henri Lebesgue. Quelques conséquences simple de la formula d'Euler. Journal de Mathématiques Pures et Appliquées, 19:27-43, 1940. Google Scholar
  9. Joseph O'Rourke. Galleries need fewer mobile guards: a variation on chvatal’s theorem. Geometriae Dedicata, 14:273-283, 1983. Google Scholar
  10. Joseph O'Rourke. Art Gallery Theorems and Algorithms. Oxford University Press, 1987. Google Scholar
  11. Jorg Sack and Jorge Urrutia, editors. Handbook of Computational Geometry. North-Holland, 2000. Google Scholar
  12. Thomas C. Shermer. Recent results in art galleries. Proceedings of IEEE, 80:1384-1399, 1992. Google Scholar
  13. Csaba D. Toth, Joseph O'Rourke, and Jacob E. Goodman, editors. Handbook of Discrete and Computational Geometry. CRC Press, 2017. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact