×

Coloring polygon visibility graphs and their generalizations. (English) Zbl 1512.05134

Summary: 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 \(\omega\) has chromatic number at most \(3 \cdot 4^{\omega - 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 coloring with the claimed number of colors can be computed in polynomial time.

MSC:

05C15 Coloring of graphs and hypergraphs
05C75 Structural characterization of families of graphs
68Q25 Analysis of algorithms and problem complexity
68U10 Computing methodologies for image processing
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abello, James; Egecioglu, Ömer; Kumar, Krishna, Visibility graphs of staircase polygons and the weak Bruhat order, I: from visibility graphs to maximal chains, Discrete Comput. Geom., 14, 3, 331-358 (1995) · Zbl 0835.05065
[2] Abello, James; Kumar, Krishna, Visibility graphs and oriented matroids, Discrete Comput. Geom., 28, 4, 449-465 (2002) · Zbl 1009.68097
[3] Ameer, Safwa; Gibson-Lopez, Matt; Krohn, Erik; Soderman, Sean; Wang, Qing, Terrain visibility graphs: persistence is not enough, (Cabello, Sergio; Chen, Danny Z., 36th International Symposium on Computational Geometry (SoCG 2020). 36th International Symposium on Computational Geometry (SoCG 2020), Leibniz International Proceedings in Informatics (LIPIcs), vol. 164 (2020), Schloss Dagstuhl-Leibniz-Zentrum für Informatik: Schloss Dagstuhl-Leibniz-Zentrum für Informatik Wadern), Article 6 pp.
[4] Ameer, Safwa; Gibson-Lopez, Matt; Krohn, Erik; Wang, Qing, On the visibility graphs of pseudo-polygons: recognition and reconstruction, (Czumaj, Artur; Xin, Qin, 18th Scandinavian Symposium and Workshops on Algorithm Theory. 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022. 18th Scandinavian Symposium and Workshops on Algorithm Theory. 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022, Leibniz International Proceedings in Informatics (LIPIcs), vol. 227 (2022), Schloss Dagstuhl-Leibniz-Zentrum für Informatik: Schloss Dagstuhl-Leibniz-Zentrum für Informatik Wadern), Article 7 pp.
[5] Arroyo, Alan; Bensmail, Julien; Bruce Richter, R., Extending drawings of graphs to arrangements of pseudolines, (Cabello, Sergio; Chen, Danny Z., 36th International Symposium on Computational Geometry (SoCG 2020). 36th International Symposium on Computational Geometry (SoCG 2020), Leibniz International Proceedings in Informatics (LIPIcs), vol. 164 (2020), Schloss Dagstuhl-Leibniz-Zentrum für Informatik: Schloss Dagstuhl-Leibniz-Zentrum für Informatik Wadern), Article 9 pp. · Zbl 1477.68194
[6] Asplund, Edgar; Grünbaum, Branko, On a coloring problem, Math. Scand., 8, 181-188 (1960) · Zbl 0095.17002
[7] Avis, David; Rappaport, David, Computing the largest empty convex subset of a set of points, (Proceedings of the First Annual Symposium on Computational Geometry (1985), Association for Computing Machinery: Association for Computing Machinery New York), 161-167
[8] Axenovich, Maria; Rollin, Jonathan; Ueckerdt, Torsten, Chromatic number of ordered graphs with forbidden ordered subgraphs, Combinatorica, 38, 5, 1021-1043 (2018) · Zbl 1424.05072
[9] Bärtschi, Andreas; Ghosh, Subir K.; Mihalák, Matúš; Tschager, Thomas; Widmayer, Peter, Improved bounds for the conflict-free chromatic art gallery problem, (Proceedings of the Thirtieth Annual Symposium on Computational Geometry (2014), Association for Computing Machinery: Association for Computing Machinery New York), 144-153 · Zbl 1395.68286
[10] Bonnet, Édouard; Geniet, Colin; Jung Kim, Eun; Thomassé, Stéphan; Watrigant, Rémi, Twin-width III: max independent set, min dominating set, and coloring, (Bansal, Nikhil; Merelli, Emanuela; Worrell, James, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Leibniz International Proceedings in Informatics (LIPIcs), vol. 198 (2021), Schloss Dagstuhl-Leibniz-Zentrum für Informatik: Schloss Dagstuhl-Leibniz-Zentrum für Informatik Wadern), Article 35 pp.
[11] Briański, Marcin; Davies, James; Walczak, Bartosz, Separating polynomial χ-boundedness from χ-boundedness (2022)
[12] Çağırıcı, Onur; Ghosh, Subir K.; Hliněný, Petr; Roy, Bodhayan, On conflict-free chromatic guarding of simple polygons, (Li, Yingshu; Cardei, Mihaela; Huang, Yan, Combinatorial Optimization and Applications. Combinatorial Optimization and Applications, Lecture Notes in Computer Science, vol. 11949 (2019), Springer: Springer Cham), 601-612 · Zbl 1435.68339
[13] Çağırıcı, Onur; Hliněný, Petr; Roy, Bodhayan, On colourability of polygon visibility graphs (2019) · Zbl 1491.68256
[14] Cardinal, Jean; Hoffmann, Udo, Recognition and complexity of point visibility graphs, Discrete Comput. Geom., 57, 1, 164-178 (2017) · Zbl 1356.05095
[15] Catanzaro, Daniele; Chaplick, Steven; Felsner, Stefan; Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Hixon, Thomas; Stacho, Juraj, Max point-tolerance graphs, Discrete Appl. Math., 216, 1, 84-97 (2017) · Zbl 1350.05118
[16] Chudnovsky, Maria; Scott, Alex; Seymour, Paul, Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings, J. Comb. Theory, Ser. B, 150, 195-243 (2021) · Zbl 1467.05069
[17] Dean, Alice M.; Evans, William; Gethner, Ellen; Laison, Joshua D.; Safari, Mohammad Ali; Trotter, William T., Bar k-visibility graphs: bounds on the number of edges, chromatic number, and thickness, (Healy, Patrick; Nikolov, Nikola S., Graph Drawing. Graph Drawing, Lecture Notes in Computer Science, vol. 3843 (2006), Springer: Springer Berlin, Heidelberg), 73-82 · Zbl 1171.68601
[18] Eidenbenz, Stephan; Stamm, Christoph, Maximum clique and minimum clique partition in visibility graphs, (van Leeuwen, Jan; Watanabe, Osamu; Hagiya, Masami; Mosses, Peter D.; Ito, Takayasu, Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics (2000), Springer: Springer Berlin, Heidelberg), 200-212 · Zbl 0998.68091
[19] Esperet, Louis, Graph Colorings, Flows and Perfect Matchings (2017), Université Grenoble Alpes, Habilitation thesis
[20] Evans, William S.; Saeedi, Noushin, On characterizing terrain visibility graphs, J. Comput. Geom., 6, 1, 108-141 (2015) · Zbl 1405.68415
[21] Ghosh, Subir K., On recognizing and characterizing visibility graphs of simple polygons, Discrete Comput. Geom., 17, 2, 143-162 (1997) · Zbl 0871.68175
[22] Ghosh, Subir K.; Goswami, Partha P., Unsolved problems in visibility graphs of points, segments, and polygons, ACM Comput. Surv., 46, 2, Article 22 pp. (2013) · Zbl 1288.05056
[23] Ghosh, Subir K.; Shermer, Thomas C.; Bhattacharya, Binay K.; Goswami, Partha P., Computing the maximum clique in the visibility graph of a simple polygon, J. Discret. Algorithms, 5, 3, 524-532 (2007) · Zbl 1129.05048
[24] Gyárfás, András, On the chromatic number of multiple interval graphs and overlap graphs, Discrete Math., 55, 2, 161-166 (1985) · Zbl 0569.05019
[25] Kára, Jan; Pór, Attila; Wood, David R., On the chromatic number of the visibility graph of a set of points in the plane, Discrete Comput. Geom., 34, 3, 497-506 (2005) · Zbl 1074.05036
[26] Levi, Friedrich, Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade, Ber. Verh. K. Sächs. Ges. Wiss. Leipz., Math.-Phys. Kl., 78, 256-267 (1926) · JFM 52.0575.01
[27] Luccio, Fabrizio; Mazzone, Silvia; Kuen Wong, Chak, A note on visibility graphs, Discrete Math., 64, 2, 209-219 (1987) · Zbl 0638.05050
[28] O’Rourke, Joseph; Streinu, Ileana, Vertex-edge pseudo-visibility graphs: characterization and recognition, (Proceedings of the Thirteenth Annual Symposium on Computational Geometry (1997), Association for Computing Machinery: Association for Computing Machinery New York), 119-128
[29] Pach, János; Tomon, István, On the chromatic number of disjointness graphs of curves, J. Comb. Theory, Ser. B, 144, 167-190 (2020) · Zbl 1443.05075
[30] Pawlik, Arkadiusz; Kozik, Jakub; Krawczyk, Tomasz; Lasoń, Michał; Micek, Piotr; Trotter, William T.; Walczak, Bartosz, Triangle-free intersection graphs of line segments with large chromatic number, J. Comb. Theory, Ser. B, 105, 6-10 (2014) · Zbl 1300.05106
[31] Pfender, Florian, Visibility graphs of point sets in the plane, Discrete Comput. Geom., 39, 1-3, 455-459 (2008) · Zbl 1145.05023
[32] Rok, Alexandre; Walczak, Bartosz, Coloring curves that cross a fixed curve, Discrete Comput. Geom., 61, 4, 830-851 (2019) · Zbl 1411.05190
[33] Rok, Alexandre; Walczak, Bartosz, Outerstring graphs are χ-bounded, SIAM J. Discrete Math., 33, 4, 2181-2199 (2019) · Zbl 1427.05149
[34] Scott, Alex; Seymour, Paul, Induced subgraphs of graphs with large chromatic number. VI. Banana trees, J. Comb. Theory, Ser. B, 145, 487-510 (2020) · Zbl 1448.05145
[35] Streinu, Ileana, Non-stretchable pseudo-visibility graphs, Comput. Geom., 31, 3, 195-206 (2005) · Zbl 1101.68736
[36] Suri, Subhash, A linear time algorithm for minimum link paths inside a simple polygon, Comput. Vis. Graph. Image Process., 35, 1, 99-110 (1986) · Zbl 0624.68101
[37] István Tomon, Personal communication.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.