The Complexity of Helly-$B_{1}$ EPG Graph Recognition
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...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2020-06-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/5603/pdf |
| _version_ | 1797270038984523776 |
|---|---|
| author | Claudson F. Bornstein Martin Charles Golumbic Tanilson D. Santos Uéverton S. Souza Jayme L. Szwarcfiter |
| author_facet | Claudson F. Bornstein Martin Charles Golumbic Tanilson D. Santos Uéverton S. Souza Jayme L. Szwarcfiter |
| author_sort | Claudson F. Bornstein |
| collection | DOAJ |
| description | 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 $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. |
| first_indexed | 2024-04-25T01:57:55Z |
| format | Article |
| id | doaj.art-da06a09c50fb450c9c4cd64e40660d25 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:55Z |
| publishDate | 2020-06-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-da06a09c50fb450c9c4cd64e40660d252024-03-07T15:40:51ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502020-06-01vol. 22 no. 1Graph Theory10.23638/DMTCS-22-1-195603The Complexity of Helly-$B_{1}$ EPG Graph RecognitionClaudson F. BornsteinMartin Charles GolumbicTanilson D. SantosUéverton S. SouzaJayme L. SzwarcfiterGolumbic, 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 $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.https://dmtcs.episciences.org/5603/pdfcomputer science - discrete mathematicscomputer science - computational complexitycomputer science - data structures and algorithms |
| spellingShingle | Claudson F. Bornstein Martin Charles Golumbic Tanilson D. Santos Uéverton S. Souza Jayme L. Szwarcfiter The Complexity of Helly-$B_{1}$ EPG Graph Recognition Discrete Mathematics & Theoretical Computer Science computer science - discrete mathematics computer science - computational complexity computer science - data structures and algorithms |
| title | The Complexity of Helly-$B_{1}$ EPG Graph Recognition |
| title_full | The Complexity of Helly-$B_{1}$ EPG Graph Recognition |
| title_fullStr | The Complexity of Helly-$B_{1}$ EPG Graph Recognition |
| title_full_unstemmed | The Complexity of Helly-$B_{1}$ EPG Graph Recognition |
| title_short | The Complexity of Helly-$B_{1}$ EPG Graph Recognition |
| title_sort | complexity of helly b 1 epg graph recognition |
| topic | computer science - discrete mathematics computer science - computational complexity computer science - data structures and algorithms |
| url | https://dmtcs.episciences.org/5603/pdf |
| work_keys_str_mv | AT claudsonfbornstein thecomplexityofhellyb1epggraphrecognition AT martincharlesgolumbic thecomplexityofhellyb1epggraphrecognition AT tanilsondsantos thecomplexityofhellyb1epggraphrecognition AT uevertonssouza thecomplexityofhellyb1epggraphrecognition AT jaymelszwarcfiter thecomplexityofhellyb1epggraphrecognition AT claudsonfbornstein complexityofhellyb1epggraphrecognition AT martincharlesgolumbic complexityofhellyb1epggraphrecognition AT tanilsondsantos complexityofhellyb1epggraphrecognition AT uevertonssouza complexityofhellyb1epggraphrecognition AT jaymelszwarcfiter complexityofhellyb1epggraphrecognition |