Document Open Access Logo

On Colourability of Polygon Visibility Graphs

Authors Onur Cagirici, Petr Hlinený, Bodhayan Roy

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2017.21.pdf
  • Filesize: 0.59 MB
  • 14 pages

Document Identifiers

Author Details

Onur Cagirici
Petr Hlinený
Bodhayan Roy

Cite As Get BibTex

Onur Cagirici, Petr Hlinený, and Bodhayan Roy. On Colourability of Polygon Visibility Graphs. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FSTTCS.2017.21

Abstract

We study the problem of colouring the visibility graphs of polygons. In particular, we provide
a polynomial algorithm for 4-colouring of the polygon visibility graphs, and prove that the 6-
colourability question is already NP-complete for them.

Subject Classification

Keywords
  • polygon visibility graph
  • graph coloring
  • NP-completeness

Metrics

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

References

  1. Oswin Aichholzer, Greg Aloupis, Erik D. Demaine, Martin L. Demaine, Vida Dujmovic, Ferran Hurtado, and Günter Rote, André Schulz, Diane L. Souvaine, and Andrew Winslow Anna Lubiw. Convexifying polygons without losing visibilities. In CCCG, 2011. Google Scholar
  2. Martin Aigner and M. Fromme. A game of cops and robbers. Discrete Applied Mathematics, 8(1):1-12, 1984. URL: http://dx.doi.org/10.1016/0166-218X(84)90073-8.
  3. Matthew Babbitt, Jesse Geneson, and Tanya Khovanova. On k-visibility graphs. Journal of Graph Algorithms and Applications, 19(1):345-360, 2015. Google Scholar
  4. Andreas Bärtschi, Subir Kumar Ghosh, Matúš Mihalák, Thomas Tschager, and Peter Widmayer. Improved bounds for the conflict-free chromatic art gallery problem. In Proceedings of the Thirtieth Annual Symposium on Computational Geometry, SOCG'14, pages 144:144-144:153, New York, NY, USA, 2014. Google Scholar
  5. A. A. Diwan and B. Roy. On Colouring Point Visibility Graphs. Proceedings of the 3rd Conference on Algorithms and Discrete Applied Mathematics, pages 156-165, 2017 (Manuscript updated later - arXiv:1610.00952. Google Scholar
  6. Sándor P. Fekete, Stephan Friedrichs, Michael Hemmer, Joseph B. M. Mitchell, and Christiane Schmidt. On the chromatic art gallery problem. In Proceedings of the 26th Canadian Conference on Computational Geometry, CCCG 2014, Halifax, Nova Scotia, Canada, 2014, 2014. Google Scholar
  7. Subir Ghosh. Visibility Algorithms in the Plane. Cambridge University Press, New York, NY, USA, 2007. Google Scholar
  8. J. Hershberger. Finding the visibility graph of a polygon in time proportional to its size. Algorithmica, 4:141-155, 1989. Google Scholar
  9. Frank Hoffmann, Klaus Kriegel, Subhash Suri, Kevin Verbeek, and Max Willert. Tight Bounds for Conflict-Free Chromatic Guarding of Orthogonal Art Galleries. In Lars Arge and János Pach, editors, 31st International Symposium on Computational Geometry (SoCG 2015), volume 34 of Leibniz International Proceedings in Informatics (LIPIcs), pages 421-435, 2015. Google Scholar
  10. J. Kára, A. Pór, and D. R. Wood. On the Chromatic Number of the Visibility Graph of a Set of Points in the Plane. Discrete and Computational Geometry, 34(3):497-506, 2005. Google Scholar
  11. Jean-Claude Latombe. Robot Motion Planning. Kluwer Academic Publishers, Norwell, MA, USA, 1991. Google Scholar
  12. D. T. Lee and A. K. Lin. Computational Complexity of Art Gallery Problems. IEEE Transactions on Information Theory, 32(2):276-282, 1986. Google Scholar
  13. Yaw-Ling Lin and Steven Skiena. Complexity aspects of visibility graphs. International Journal of Computational Geometry and Applications, 5:289-312, 1995. Google Scholar
  14. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979. Google Scholar
  15. J. O'Rourke. Art Gallery Theorems and Algorithms. Oxford University Press, New York, 1987. Google Scholar
  16. J. O'Rourke and K. Supowit. Some NP-hard polygon decomposition problems. IEEE Transactions on Information Theory, 29:181-190, 1983. Google Scholar
  17. Joseph O'Rourke and Ileana Streinu. The vertex-edge visibility graph of a polygon. Computational Geometry, 10(2):105-120, 1998. Google Scholar
  18. F. Pfender. Visibility Graphs of Point Sets in the Plane. Discrete and Computational Geometry, 39(1):455-459, 2008. Google Scholar
  19. S. K. Ghosh and T. Shermer and B. K. Bhattacharya and P. P. Goswami. Computing the maximum clique in the visibility graph of a simple polygon. Journal of Discrete Algorithms, 5:524-532, 2007. Google Scholar
  20. T. Shermer. Hiding people in polygons. Computing, 42:109-131, 1989. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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