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.
