AT-free, coAT-free Graphs and AT-free Posets

not available

graph, algorithm, asteroidal triple-free, AT-free, minimal separator

In this extended abstract we consider structural and algorithmic properties of two graph classes which share the property that they are on the one hand generalizations of permutation graphs, on the other hand subfamilies of AT-free graphs.

First we consider graphs that are AT-free and coAT-free. We show that the number of minimal separators in an AT-free, coAT-free graph is bounded by a polynomial in the number of vertices of the graph. From this it follows that problems like treewidth}, pathwidth}, minimum fill-in}, minimum interval graph completion}, and vertex ranking} become solvable in polynomial time for AT-free, coAT-free graphs.

The second part of the paper is devoted to AT-free posets, i.e. comparability graphs not containing an asteroidal triple. We study the relationship between dominating pair vertices and extremal elements (i.e. minimal or maximal elements) of a given AT-free poset. Furthermore we suggest an ordering for posets that visualizes the overall structure of AT-free posets.

Download as [PDF] [ps.gz]