Back to Search
Start Over
The Complexity of Helly-B1-EPG graph Recognition.
- Source :
-
Discrete Mathematics & Theoretical Computer Science (DMTCS) . 2020, Vol. 22 Issue 1, p1-24. 24p. - Publication Year :
- 2020
-
Abstract
- Golumbic, Lipshteyn, and Stern defined in 2009 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 Bk-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 Bk-EPG representation whose edge-intersections of paths satisfy the Helly property, so-called Helly-Bk-EPG representation, is in NP, for every k bounded by a polynomial function of jV (G)j. Moreover, we show that the problem of recognizing Helly-B1-EPG graphs is NP-complete, and it remains NP-complete even when restricted to 2-apex and 3-degenerate graphs. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 13658050
- Volume :
- 22
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics & Theoretical Computer Science (DMTCS)
- Publication Type :
- Academic Journal
- Accession number :
- 145502951