×

String graphs of \(k\)-bend paths on a grid. (English) Zbl 1268.05134

Bonomo, Flavia (ed.) et al., LAGOS’11 – VI Latin-American algorithms, graphs, and optimization symposium. Extended abstracts from the symposium, Bariloche, Argentina, March 28–April 1, 2011. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 37, 141-146 (2011).
Summary: We investigate the class of vertex intersection graphs of paths on a grid, and specifically consider the subclasses that are obtained when each path in the representation has at most \(k\) bends (turns). We call such a subclass the \(B_{k}\)-VPG graphs, \(k\geq 0\).
We present a complete hierarchy of VPG graphs relating them to other known families of graphs. String graphs are equivalent to VPG graphs. The grid intersection graphs [S. Bellantoni et al., Discrete Math. 114, No. 1–3, 41–49 (1993; Zbl 0784.05031); I. B.-A. Hartman, I. Newman, and R. Ziv, Discrete Math. 87, No. 1, 41–52 (1991; Zbl 0739.05081)] are shown to be equivalent to the bipartite \(B_{0}\)-VPG graphs. Chordal \(B_{0}\)-VPG graphs are shown to be exactly strongly chordal \(B_{0}\)-VPG graphs. We prove the strict containment of \(B_{0}\)-VPG and circle graphs into \(B_{1}\)-VPG. Planar graphs are known to be in the class of string graphs, and we prove here that planar graphs are \(B_{3}\)-VPG graphs.
In the case of \(B_{0}\)-VPG graphs, we observe that a set of horizontal and vertical segments have strong Helly number 2. We show that the coloring problem for \(B_{k}\)-VPG graphs, for \(k\geq 00\), is NP-complete and give a 2-approximation algorithm for coloring \(B_{0}\)-VPG graphs. Furthermore, we prove that triangle-free \(B_{0}\)-VPG graphs are 4-colorable, and this is best possible.
For the entire collection see [Zbl 1239.05004].

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Asinowski, E. Cohen, M.C. Golumbic, V. Limouzy, M. Lipshteyn, M. Stern, Intersection Graphs of Paths on a Grid, Technical report, November 2010.; A. Asinowski, E. Cohen, M.C. Golumbic, V. Limouzy, M. Lipshteyn, M. Stern, Intersection Graphs of Paths on a Grid, Technical report, November 2010. · Zbl 1254.68184
[2] Bandy, M.; Sarrafzadeh, M., Stretching a knock-knee layout for multilayer wiring, IEEE Trans Comput, 39, 148-151 (1990)
[3] Bellantoni, S.; Hartman, I. B.-A.; Przytycka, T.; Whitesides, S., Grid intersection graphs and boxicity, Discrete Math., 114, 41-49 (1993) · Zbl 0784.05031
[4] Hartman, I. B.-A.; Newman, I.; Ziv, R., On grid intersection graphs, Discrete Math., 87, 1, 41-52 (1991) · Zbl 0739.05081
[5] Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam · Zbl 0483.05029
[6] Biedl, T.; Stern, M., On edge-intersection graphs of k-bend paths in grids, Proc. COCOON ʼ09. Proc. COCOON ʼ09, LNCS, 5609, 8695 (2009)
[7] Coury, M. D.; Hell, P.; Kratochvíl, J.; Vyskocil, T., Faithful Representations of Graphs by Islands in the Extended Grid, Proc. LATIN ʼ10. Proc. LATIN ʼ10, LNCS, 6034, 131-142 (2010) · Zbl 1283.68269
[8] Czemerinski, H.; Durn, G.; Gravano, A., Bouchet graphs: a generalization of circle graphs, Congressus Numerantium, 155, 95-108 (2002) · Zbl 1021.05086
[9] Ehrlich, G.; Even, S.; Tarjan, R., Intersection graphs of curves in the plane, Journal of Combinatorial Theory Series B, 21, 8-20 (1976) · Zbl 0348.05113
[10] Farber, M., Characterizations of strongly chordal graphs, Discrete Math., 43, 173-189 (1983) · Zbl 0514.05048
[11] Garey, M.; Johnson, D.; Miller, G.; Papadimitriou, C., The complexity of coloring circular arcs and chords, SIAM Journal on Algebraic and Discrete Methods, 1, 216-227 (1980) · Zbl 0499.05058
[12] Kratochvíl, J.; String Graphs, I., The number of critical nonstring graphs is infinite, Journal of Combinatorial Theory B, 52, 53-66 (1991) · Zbl 0675.05058
[13] Kratochvíl, J., A special planar satisfiability problem and a consequence of its NP-completeness, Discrete Applied Math., 52, 233-252 (1994) · Zbl 0810.68083
[14] Kratochvíl, J.; Matousek, J., Intersection graphs of segments, Journal of Combinatorial Theory B, 68, 289-315 (1994) · Zbl 0808.68075
[15] Molitor, P., A survey on wiring, EIK Journal of Information Processing and Cybernetics, 27, 1, 3-19 (1991) · Zbl 0718.94016
[16] Sinden, F., Topology of thin film circuits, Bell Sys. Tech. J., 45, 1639-1662 (1966) · Zbl 0144.45601
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.