Graphs of edge-intersecting non-splitting paths

Abstract

In this work, we introduce and study a new graph class: namely the graphs of Edge-Intersecting Non-Splitting Paths (ENP). First, we consider a special case where the host graph is a tree: the graphs of Edge-Intersecting Non-Splitting Paths in a Tree (ENPT). We study the characterization of the ENPT representations of chordless cycles (holes) which are one of the important basic graph structures. Under some assumption, we give an algorithm that returns the unique minimal representation if it exists. However, we show that the problem is NP-complete in general that is when this assumption does not necessarily hold. Then, we consider a more general case for which the host graph can be an arbitrary graph. As opposed to the Edge Intersection Graphs of Paths in an arbitrary graph which includes all graphs, we show that this is not true for ENP that is there exist some graphs which are not ENP. We also show that the class ENP coincides with the family of graphs of Edge-Intersecting and Non-Splitting Paths in a Grid (ENPG). Following similar studies for EPG graph class, we study the implications of restricting the number of bends of the individual paths in the grid. We show that restricting the number of bends also restricts the graph class. More concretely, by restricting the number of bends one gets an infinite sequence of classes such that every class is properly included in the next one. In particular, we show that one bend ENPG graphs are properly included in two bend ENPG graphs. In addition, we show that trees and cycles are one bend ENPG graphs, and characterize split graphs and co-bipartite graphs that are one bend ENPG. We prove that the recognition problem of one bend ENPG graphs is NP-complete even in a very restricted subclass of split graphs. Last, we provide a linear time recognition algorithm for one bend ENPG co-bipartite graphs.