Constant Threshold Intersection Graphs of Orthodox Paths in Trees

Abstract

A graph $G$ belongs to the class $\mathrm{ORTH}[h,s,t]$ for integers $h$, $s$, and $t$ if there is a pair $(T,\mathcal{S})$, where $T$ is a tree of maximum degree at most $h$, and $\mathcal{S}$ is a collection $(S_u{)}_{u\in V(G)}$ of subtrees $S_u$ of maximum degree at most $s$ of $T$, one for each vertex $u$ of $G$, such that, for every vertex $u$ of $G$, all leaves of $S_u$ are also leaves of $T$, and, for every two distinct vertices $u$ and $v$ of $G$, the following three properties are equivalent: (i) $u$ and $v$ are adjacent. (ii) $S_u$ and $S_v$ have at least $t$ vertices in common. (iii) $S_u$ and $S_v$ share a leaf of $T$. The class $\mathrm{ORTH}[h,s,t]$ was introduced by Jamison and Mulder. Here we focus on the case $s=2$, which is closely related to the well-known VPT and EPT graphs. We collect general properties of the graphs in $\mathrm{ORTH}[h,2,t]$, and provide a characterization in terms of tree layouts. Answering a question posed by Golumbic, Lipshteyn, and Stern, we show that $\mathrm{ORTH}[h+1,2,t]\setminus \mathrm{ORTH}[h,2,t]$ is non-empty for every $h\ge 3$ and $t\ge 3$. We derive decomposition properties, which lead to efficient recognition algorithms for the graphs in $\mathrm{ORTH}[h,2,2]$ for every $h\ge 3$. Finally, we give a complete description of the graphs in $\mathrm{ORTH}[3,2,2]$, and show that the graphs in $\mathrm{ORTH}[3,2,3]$ are line graphs of planar graphs.