Document Open Access Logo

Colouring Polygon Visibility Graphs and Their Generalizations

Authors James Davies, Tomasz Krawczyk, Rose McCarty, Bartosz Walczak

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.29.pdf
  • Filesize: 0.65 MB
  • 16 pages

Document Identifiers

Author Details

James Davies
  • Department of Combinatorics and Optimization, School of Mathematics, University of Waterloo, Canada
Tomasz Krawczyk
  • Department of Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland
Rose McCarty
  • Department of Combinatorics and Optimization, School of Mathematics, University of Waterloo, Canada
Bartosz Walczak
  • Department of Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland

Funding

Tomasz Krawczyk and Bartosz Walczak were partially supported by the National Science Centre of Poland grant 2015/17/D/ST1/00585.

Acknowledgements

We thank Bodhayan Roy for sharing the problem of whether polygon visibility graphs are χ-bounded.

Cite AsGet BibTex

James Davies, Tomasz Krawczyk, Rose McCarty, and Bartosz Walczak. Colouring Polygon Visibility Graphs and Their Generalizations. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.29

Abstract

Curve pseudo-visibility graphs generalize polygon and pseudo-polygon visibility graphs and form a hereditary class of graphs. We prove that every curve pseudo-visibility graph with clique number ω has chromatic number at most 3⋅4^{ω-1}. The proof is carried through in the setting of ordered graphs; we identify two conditions satisfied by every curve pseudo-visibility graph (considered as an ordered graph) and prove that they are sufficient for the claimed bound. The proof is algorithmic: both the clique number and a colouring with the claimed number of colours can be computed in polynomial time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Visibility graphs
  • χ-boundedness
  • pseudoline arrangements
  • ordered graphs

Metrics

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

Related Versions

References

  1. James Abello, Ömer Egecioglu, and Krishna Kumar. Visibility graphs of staircase polygons and the weak Bruhat order, I: from visibility graphs to maximal chains. Discrete & Computational Geometry, 14(3):331-358, 1995. Google Scholar
  2. James Abello and Krishna Kumar. Visibility graphs and oriented matroids. Discrete & Computational Geometry, 28(4):449-465, 2002. Google Scholar
  3. Safwa Ameer, Matt Gibson-Lopez, Erik Krohn, Sean Soderman, and Qing Wang. Terrain visibility graphs: persistence is not enough. In Sergio Cabello and Danny Z. Chen, editors, 36th International Symposium on Computational Geometry (SoCG 2020), volume 164 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1-6:13. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Wadern, 2020. Google Scholar
  4. Alan Arroyo, Julien Bensmail, and R. Bruce Richter. Extending drawings of graphs to arrangements of pseudolines. In Sergio Cabello and Danny Z. Chen, editors, 36th International Symposium on Computational Geometry (SoCG 2020), volume 164 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1-9:14. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Wadern, 2020. Google Scholar
  5. Edgar Asplund and Branko Grünbaum. On a coloring problem. Mathematica Scandinavica, 8:181-188, 1960. Google Scholar
  6. David Avis and David Rappaport. Computing the largest empty convex subset of a set of points. In Proceedings of the First Annual Symposium on Computational Geometry, pages 161-167. Association for Computing Machinery, New York, 1985. Google Scholar
  7. Maria Axenovich, Jonathan Rollin, and Torsten Ueckerdt. Chromatic number of ordered graphs with forbidden ordered subgraphs. Combinatorica, 38(5):1021-1043, 2018. Google Scholar
  8. Andreas BartschiBärtschi, Subir K. 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, pages 144-153. Association for Computing Machinery, New York, 2014. Google Scholar
  9. Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width III: max independent set and coloring. arXiv, 2020. URL: http://arxiv.org/abs/2007.14161.
  10. Onur CagiriciÇağırıcı, Petr Hliněný, Subir K. Ghosh, and Bodhayan Roy. On conflict-free chromatic guarding of simple polygons. In Yingshu Li, Mihaela Cardei, and Yan Huang, editors, Combinatorial Optimization and Applications, volume 11949 of Lecture Notes in Computer Science, pages 601-612. Springer, Cham, 2019. Google Scholar
  11. Onur CagiriciÇağırıcı, Petr Hliněný, and Bodhayan Roy. On colourability of polygon visibility graphs. arXiv, 2019. URL: http://arxiv.org/abs/1906.01904.
  12. Jean Cardinal and Udo Hoffmann. Recognition and complexity of point visibility graphs. Discrete & Computational Geometry, 57(1):164-178, 2017. Google Scholar
  13. Daniele Catanzaro, Steven Chaplick, Stefan Felsner, Bjarni V. Halldórsson, Magnús M. Halldórsson, Thomas Hixon, and Juraj Stacho. Max point-tolerance graphs. Discrete Applied Mathematics, 216(1):84-97, 2017. Google Scholar
  14. Maria Chudnovsky, Alex Scott, and Paul Seymour. Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings. arXiv, 2016. URL: http://arxiv.org/abs/1609.00314.
  15. Alice M. Dean, William Evans, Ellen Gethner, Joshua D. Laison, Mohammad Ali Safari, and William T. Trotter. Bar k-visibility graphs: bounds on the number of edges, chromatic number, and thickness. In Patrick Healy and Nikola S. Nikolov, editors, Graph Drawing, volume 3843 of Lecture Notes in Computer Science, pages 73-82. Springer, Berlin, Heidelberg, 2006. Google Scholar
  16. Stephan Eidenbenz and Christoph Stamm. Maximum clique and minimum clique partition in visibility graphs. In Jan van Leeuwen, Osamu Watanabe, Masami Hagiya, Peter D. Mosses, and Takayasu Ito, editors, Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics, pages 200-212. Springer, Berlin, Heidelberg, 2000. Google Scholar
  17. Louis Esperet. Graph Colorings, Flows and Perfect Matchings. Habilitation thesis, Université Grenoble Alpes, 2017. Google Scholar
  18. William S. Evans and Noushin Saeedi. On characterizing terrain visibility graphs. Journal of Computational Geometry, 6(1):108-141, 2015. Google Scholar
  19. Subir K. Ghosh. On recognizing and characterizing visibility graphs of simple polygons. Discrete & Computational Geometry, 17(2):143-162, 1997. Google Scholar
  20. Subir K. Ghosh and Partha P. Goswami. Unsolved problems in visibility graphs of points, segments, and polygons. ACM Computing Surveys, 46(2):Article 22, 2013. Google Scholar
  21. Subir K. Ghosh, Thomas C. Shermer, Binay K. Bhattacharya, and Partha P. Goswami. Computing the maximum clique in the visibility graph of a simple polygon. Journal of Discrete Algorithms, 5(3):524-532, 2007. Google Scholar
  22. András Gyárfás. On the chromatic number of multiple interval graphs and overlap graphs. Discrete Mathematics, 55(2):161-166, 1985. Google Scholar
  23. Jan Kára, Attila Pór, and David R. Wood. On the chromatic number of the visibility graph of a set of points in the plane. Discrete & Computational Geometry, 34(3):497-506, 2005. Google Scholar
  24. Friedrich Levi. Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade. Berichte über die Verhandlungen der Königlich-Sächsischen Gesellschaft der Wissenschaften zu Leipzig, Mathematisch-Physische Klasse, 78:256-267, 1926. Google Scholar
  25. Fabrizio Luccio, Silvia Mazzone, and Chak Kuen Wong. A note on visibility graphs. Discrete Mathematics, 64(2):209-219, 1987. Google Scholar
  26. Joseph O'Rourke and Ileana Streinu. Vertex-edge pseudo-visibility graphs: characterization and recognition. In Proceedings of the Thirteenth Annual Symposium on Computational Geometry, pages 119-128. Association for Computing Machinery, New York, 1997. Google Scholar
  27. János Pach and István Tomon. On the chromatic number of disjointness graphs of curves. Journal of Combinatorial Theory, Series B, 144:167-190, 2020. Google Scholar
  28. Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Michał Lasoń, Piotr Micek, William T. Trotter, and Bartosz Walczak. Triangle-free intersection graphs of line segments with large chromatic number. Journal of Combinatorial Theory, Series B, 105:6-10, 2014. Google Scholar
  29. Florian Pfender. Visibility graphs of point sets in the plane. Discrete & Computational Geometry, 39(1-3):455-459, 2008. Google Scholar
  30. Alexandre Rok and Bartosz Walczak. Coloring curves that cross a fixed curve. Discrete & Computational Geometry, 61(4):830-851, 2019. Google Scholar
  31. Alexandre Rok and Bartosz Walczak. Outerstring graphs are χ-bounded. SIAM Journal on Discrete Mathematics, 33(4):2181-2199, 2019. Google Scholar
  32. Alex Scott and Paul Seymour. Induced subgraphs of graphs with large chromatic number. VI. Banana trees. Journal of Combinatorial Theory, Series B, 145:487-510, 2020. Google Scholar
  33. Ileana Streinu. Non-stretchable pseudo-visibility graphs. Computational Geometry, 31(3):195-206, 2005. Google Scholar
  34. Subhash Suri. A linear time algorithm for minimum link paths inside a simple polygon. Computer Vision, Graphics, and Image Processing, 35(1):99-110, 1986. Google Scholar
  35. István Tomon. personal communication. 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 Imprint Privacy Contact