×

The complexity of Helly-\(B_1\) EPG graph recognition. (English) Zbl 1454.05059

Summary: M. C. Golumbic et al. [Networks 54, No. 3, 130–138 (2009; Zbl 1208.05090)] defined the class of EPG graphs, the intersection graph class of edge paths on a grid. An EPG graph \(G\) is a graph that admits a representation where its vertices correspond to paths in a grid \(Q\), such that two vertices of \(G\) are adjacent if and only if their corresponding paths in \(Q\) have a common edge. If the paths in the representation have at most \(k\) bends, we say that it is a \(B_k\)-EPG representation. A collection \(C\) of sets satisfies the Helly property when every sub-collection of \(C\) that is pairwise intersecting has at least one common element. In this paper, we show that given a graph \(G\) and an integer \(k\), the problem of determining whether \(G\) admits a \(B_k\)-EPG representation whose edge-intersections of paths satisfy the Helly property, so-called Helly-\(B_k\)-EPG representation, is in NP, for every \(k\) bounded by a polynomial function of \(|V(G)|\). Moreover, we show that the problem of recognizing Helly-\(B_1\)-EPG graphs is NP-complete, and it remains NP-complete even when restricted to 2-apex and 3-degenerate graphs.

MSC:

05C38 Paths and cycles

Citations:

Zbl 1208.05090
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] L. Alc´on, F. Bonomo, G. Dur´an, M. Gutierrez, M. P. Mazzoleni, B. Ries, and M. Valencia-Pabon. On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid.Discrete Applied Mathematics, 234:12-21, 2016. · Zbl 1441.05121
[2] A. Asinowski and A. Suk. Edge intersection graphs of systems of paths on a grid with a bounded number of bends.Discrete Applied Math, 157:3174-3180, 2009. · Zbl 1227.05200
[3] M. Bandy and M. Sarrafzadeh. Stretching a knock-knee layout for multilayer wiring.IEEE Transactions on Computers, 39:148-151, 1990.
[4] C. Berge and P. Duchet. A generalization of Gilmore’s theorem.Recent Advances in Graph Theory. Proceedings 2nd Czechoslovak Symposium,, pages 49-55, 1975. · Zbl 0325.05125
[5] K. Booth and G. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms.Journal of Computer and System Sciences, 13:335-379, 1976. · Zbl 0367.68034
[6] K. Cameron, S. Chaplick, and C. T. Ho‘ang. Edge intersection graphs of L-shaped paths in grids.Discrete Applied Mathematics, 210:185-194, 2016. · Zbl 1339.05381
[7] E. Cohen, M. C. Golumbic, and B. Ries. Characterizations of cographs as intersection graphs of paths on a grid.Discrete Applied Mathematics, 178:46-57, 2014. · Zbl 1300.05267
[8] M. C. Dourado, F. Protti, and J. L. Szwarcfiter. Complexity aspects of the Helly property: Graphs and hypergraphs.The Electronic Journal of Combinatorics (Dynamic Surveys), 17:1-53, 2009. · Zbl 1206.05002
[9] P. Duchet. Propriet´e de helly et probl‘emes de repr´esentations. InColloquium International CNRS 260, Probl´emes Combinatoires et Th´eorie de Graphs, pages 117-118, Orsay, France, 1976. · Zbl 0413.05042
[10] M. R. Garey and D. S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Company, 1979. · Zbl 0411.68039
[11] M. C. Golumbic and G. Morgenstern. Edge intersection graphs of paths on a grid. In50 years of Combinatorics, Graph Theory, and Computing, pages 193-209. Chapman and Hall/CRC, 2019. · Zbl 1454.05061
[12] M. C. Golumbic, M. Lipshteyn, and M. Stern. Edge intersection graphs of single bend paths on a grid. Networks, 54:130-138, 2009. · Zbl 1208.05090
[13] 24Bornstein, Golumbic, Santos, Souza, Szwarcfiter
[14] M. C. Golumbic, M. Lipshteyn, and M. Stern. Single bend paths on a grid have strong Helly number 4. Networks, 62:161-163, 2013. · Zbl 1338.05188
[15] D. Heldt, K. Knauer, and T. Ueckerdt. On the bend-number of planar and outerplanar graphs.Discrete Applied Mathematics, 179:109-119, 2014a. · Zbl 1303.05038
[16] D. Heldt, K. Knauer, and T. Ueckerdt. Edge-intersection graphs of grid paths: the bend-number.Discrete Applied Mathematics, 167:144-162, 2014b. · Zbl 1284.05180
[17] P. Molitor. A survey on wiring.Journal of Information Processing and Cybernetics, EIK, 27:3-19, 1991. · Zbl 0718.94016
[18] W. Mulzer and G. Rote. Minimum-weight triangulation is NP-hard.Journal of the ACM (JACM), 55(2): 11, 2008. · Zbl 1311.05134
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.