Intersection graphs of maximal sub-polygons of \(k\)-lizards. (English) Zbl 1518.05141
Summary: We introduce \(k\)-maximal sub-polygon graphs (\(k\)-MSP graphs), the intersection graphs of maximal polygons contained in a polygon with sides parallel to a regular \(2k\)-gon. We prove that all complete graphs are \(k\)-MSP graphs for all \(k>1\); trees are 2-MSP graphs; trees are \(k\)-MSP graphs for \(k>2\) if and only if they are caterpillars; and \(n\)-cycles are not \(k\)-MSP graphs for \(n>3\) and \(k>1\). We derive bounds for which \(j\)-cycles appear as induced subgraphs of \(k\)-MSP graphs. As our main result, we construct examples of graphs which are \(k\)-MSP graphs and not \(j\)-MSP graphs for all \(k>1\), \(j>1\), \(k \neq j\).
MSC:
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05C75 | Structural characterization of families of graphs |
| 05C76 | Graph operations (line graphs, products, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 05C05 | Trees |
References:
| [1] | Berge, C.; Chen, CC; Chvátal, V.; Seow, CS, Combinatorial properties of polyominoes, Combinatorica, 1, 3, 217-224 (1981) · Zbl 0491.05048 · doi:10.1007/BF02579327 |
| [2] | Bessy, S.; Bougeret, M.; Chaplick, S.; Gonçalves, D.; Paul, C., On independent set in B1-EPG graphs, Discret. Appl. Math., 278, 62-72 (2020) · Zbl 1437.05178 · doi:10.1016/j.dam.2019.10.019 |
| [3] | Church, P.: Snakes in the plane. Master’s thesis, University of Waterloo (2008) |
| [4] | Devadoss, SL; O’Rourke, J., Discrete and Computational Geometry (2011), Princeton University Press · Zbl 1232.52001 |
| [5] | Golomb, SW, Polyominoes: Puzzles, Patterns, Problems, and Packings (1996), Princeton University Press · Zbl 0831.05020 |
| [6] | Hliněnỳ, P.; Kratochvıl, J., Representing graphs by disks and balls (a survey of recognition-complexity results), Discrete Math., 229, 1-3, 101-124 (2001) · Zbl 0969.68118 · doi:10.1016/S0012-365X(00)00204-1 |
| [7] | Maire, F., A characterization of intersection graphs of the maximal rectangles of a polyomino, Discrete Math., 120, 1-3, 211-214 (1993) · Zbl 0793.05049 · doi:10.1016/0012-365X(93)90578-H |
| [8] | McKee, TA; McMorris, FR, Topics in Intersection Graph Theory (1999), SIAM · Zbl 0945.05003 · doi:10.1137/1.9780898719802 |
| [9] | O’Rourke, J., Computational Geometry in C (1998), Cambridge University Press · Zbl 0912.68201 · doi:10.1017/CBO9780511804120 |
| [10] | Pach, J.; Reed, B.; Yuditsky, Y., Almost all string graphs are intersection graphs of plane convex sets, Discrete Comput. Geom., 63, 888-917 (2020) · Zbl 1442.05189 · doi:10.1007/s00454-020-00213-z |
| [11] | Preparata, FP; Shamos, MI, Computational Geometry: An Introduction (2012), Springer Science & Business Media · Zbl 0759.68037 |
| [12] | Shearer, JB, A class of perfect graphs, SIAM J. Algebraic Discrete Methods, 3, 3, 281-284 (1982) · Zbl 0506.05049 · doi:10.1137/0603027 |
| [13] | West, DB, Introduction to Graph Theory (2001), Upper Saddle River: Prentice Hall, Upper Saddle River |
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.
