Constant Threshold Intersection Graphs of Orthodox Paths in Trees

A graph $G$ belongs to the class $\mathrm{O}\mathrm{R}\mathrm{T}\mathrm{H}[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{O}\mathrm{R}\mathrm{T}\mathrm{H}[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 ${\rm 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{O}\mathrm{R}\mathrm{T}\mathrm{H}[h+1,2,t]\setminus \mathrm{O}\mathrm{R}\mathrm{T}\mathrm{H}[h,2,t]$ is non-empty for every $h\geq 3$and$t\geq 3$. We derive decomposition properties, which lead to efficient recognition algorithms for the graphs in $\mathrm{O}\mathrm{R}\mathrm{T}\mathrm{H}[h,2,2]$ for every $h\geq 3$\mathrm{.}Finally,wegiveacompletedescriptionofthegraphsin${\rm ORTH}[3,2,2]$,andshowthatthegraphsin${\rm ORTH}[3,2,3]$ are line graphs of planar graphs.