English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper we continue the systematic study of Contact graphs of Paths ona Grid (CPG graphs) initiated in [Deniz et al., 2018]. A CPG graph is a graphfor which there exists a collection of pairwise interiorly disjoint paths on agrid in one-to-one correspondence with its vertex set such that two verticesare adjacent if and only if the corresponding paths touch at a grid-point. Ifevery such path has at most $k$ bends for some $k \geq 0$, the graph is said tobe $B_k$-CPG.  We first show that, for any $k \geq 0$, the class of $B_k$-CPG graphs isstrictly contained in the class of $B_{k+1}$-CPG graphs even within the classof planar graphs, thus implying that there exists no $k \geq 0$ such that everyplanar CPG graph is $B_k$-CPG. The main result of the paper is that recognizingCPG graphs and $B_k$-CPG graphs with $k \geq 1$ is $\mathsf{NP}$-complete.Moreover, we show that the same remains true even within the class of planargraphs in the case $k \geq 3$. We then consider several graph problemsrestricted to CPG graphs and show, in particular, that Independent Set andClique Cover remain $\mathsf{NP}$-hard for $B_0$-CPG graphs. Finally, weconsider the related classes $B_k$-EPG of edge-intersection graphs of pathswith at most $k$ bends on a grid. Although it is possible to optimally color a$B_0$-EPG graph in polynomial time, as this class coincides with that ofinterval graphs, we show that, in contrast, 3-Colorability is$\mathsf{NP}$-complete for $B_1$-EPG graphs.

CPG graphs: Some structural and hardness results