On probe permutation graphs

Abstract: Given a class of graphs , a graph is a probe graph of if its vertices can be partitioned into two sets, , the probes, and an independent set , the nonprobes, such that can be embedded into a graph of by adding edges between certain vertices of . If the partition of the vertices into probes and nonprobes is part of the input, then we call the graph a partitioned probe graph of . In this paper, we provide a recognition algorithm for partitioned probe permutation graphs with time complexity , where is the number of vertices of the input graph. We show that a probe permutation graph has at most minimal separators. As a consequence, for probe permutation graphs there exist polynomial-time algorithms solving problems like treewidth and minimum fill-in. We also characterize those graphs for which the probe graphs must be weakly chordal. [Copyright &y& Elsevier]