A representation diagram for maximal independent sets of a graph

Let H = (V(H) E(H)) be a directed graph with distinguished vertices s and t. An st-path in H is a simple directed path starting from s and ending at t. Let P(H) be defined as {S \ S is the set of vertices on an st-path in H (s and t are excluded)}. For an undirected graph G = (V(G),E(G)) with V(G) subset of or equal to V(H) - {s,t}, if the family of maximal independent sets of G coincides with P(H), we call H an MIS-diagram for G. In this paper, we provide a necessary and sufficient condition for a directed graph to be an MIS-diagram for an undirected graph. We also show that an undirected graph G has an MIS-diagram iff G is a cocomparability graph. Based on the proof of the latter result, we can construct an efficient algorithm for generating all maximal independent sets of a cocomparability graph.