Graphs of Edge-Intersecting and Non-Splitting One Bend Paths in a Grid

The families EPT (resp. EPG) Edge Intersection Graphs of Paths in a tree(resp. in a grid) are well studied graph classes. Recently we introduced thegraph classes Edge-Intersecting and Non-Splitting Paths in a Tree ENPT, and ina Grid (ENPG). It was shown that ENPG contains an infinite hierarchy ofsubclasses that are obtained by restricting the number of bends in the paths.Motivated by this result, in this work we focus on one bend {ENPG} graphs. Weshow that one bend ENPG graphs are properly included in two bend ENPG graphs.We also show that trees and cycles are one bend ENPG graphs, and characterizethe split graphs and co-bipartite graphs that are one bend ENPG. We prove thatthe recognition problem of one bend ENPG split graphs is NP-complete even in avery restricted subfamily of split graphs. Last we provide a linear timerecognition algorithm for one bend ENPG co-bipartite graphs