On probe permutation graphs

Given a class of graphs GG, a graph GG is a probe graph of  GG if its vertices can be partitioned into two sets, PP, the probes,   and an independent set NN, the nonprobes,   such that GG can be embedded into a graph of GG by adding edges between certain vertices of NN. 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  GG. In this paper, we provide a recognition algorithm for partitioned probe permutation graphs with time complexity O(n2)O(n2), where nn is the number of vertices of the input graph. We show that a probe permutation graph has at most O(n4)O(n4) 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.