Intersection Graphs of Orthodox Paths in Trees

We study the graph classes ORTH[h,s,t] introduced by Jamison and Mulder, and 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 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 ORTH[h+1,2,t]\ORTH[h,2,t] is non-empty for every h≥3 and t≥3. We derive decomposition properties, which lead to efficient recognition algorithms for the graphs in ORTH[h,2,2] for every h≥3. Finally, we show that the graphs in ORTH[3,2,3] are line graphs of planar graphs.