ﻻ يوجد ملخص باللغة العربية
In this paper we continue the study of the edge intersection graphs of one (or zero) bend paths on a rectangular grid. That is, the edge intersection graphs where each vertex is represented by one of the following shapes: $llcorner$,$ulcorner$, $urcorner$, $lrcorner$, and we consider zero bend paths (i.e., | and $-$) to be degenerate $llcorner$s. These graphs, called $B_1$-EPG graphs, were first introduced by Golumbic et al (2009). We consider the natural subclasses of $B_1$-EPG formed by the subsets of the four single bend shapes (i.e., {$llcorner$}, {$llcorner$,$ulcorner$}, {$llcorner$,$urcorner$}, and {$llcorner$,$ulcorner$,$urcorner$}) and we denote the classes by [$llcorner$], [$llcorner$,$ulcorner$], [$llcorner$,$urcorner$], and [$llcorner$,$ulcorner$,$urcorner$] respectively. Note: all other subsets are isomorphic to these up to 90 degree rotation. We show that testing for membership in each of these classes is NP-complete and observe the expected strict inclusions and incomparability (i.e., [$llcorner$] $subsetneq$ [$llcorner$,$ulcorner$], [$llcorner$,$urcorner$] $subsetneq$ [$llcorner$,$ulcorner$,$urcorner$] $subsetneq$ $B_1$-EPG; also, [$llcorner$,$ulcorner$] is incomparable with [$llcorner$,$urcorner$]). Additionally, we give characterizations and polytime recognition algorithms for special subclasses of Split $cap$ [$llcorner$].
We consider the NP-complete problem of tracking paths in a graph, first introduced by Banik et. al. [3]. Given an undirected graph with a source $s$ and a destination $t$, find the smallest subset of vertices whose intersection with any $s-t$ path re
Given a graph, the shortest-path problem requires finding a sequence of edges with minimum cumulative length that connects a source vertex to a target vertex. We consider a generalization of this classical problem in which the position of each vertex
Bir{o} et al. (1992) introduced $H$-graphs, intersection graphs of connected subgraphs of a subdivision of a graph $H$. They are related to many classes of geometric intersection graphs, e.g., interval graphs, circular-arc graphs, split graphs, and c
A graph $G$ is said to be the intersection of graphs $G_1,G_2,ldots,G_k$ if $V(G)=V(G_1)=V(G_2)=cdots=V(G_k)$ and $E(G)=E(G_1)cap E(G_2)capcdotscap E(G_k)$. For a graph $G$, $mathrm{dim}_{COG}(G)$ (resp. $mathrm{dim}_{TH}(G)$) denotes the minimum num
In 1966, Gallai asked whether all longest paths in a connected graph share a common vertex. Counterexamples indicate that this is not true in general. However, Gallais question is positive for certain well-known classes of connected graphs, such as s