  We prove a characterization of all polynomial-time computable queries on the
class of interval graphs by sentences of fixed-point logic with counting. More
precisely, it is shown that on the class of unordered interval graphs, any
query is polynomial-time computable if and only if it is definable in
fixed-point logic with counting. This result is one of the first establishing
the capturing of polynomial time on a graph class which is defined by forbidden
induced subgraphs. For this, we define a canonical form of interval graphs
using a type of modular decomposition, which is different from the method of
tree decomposition that is used in most known capturing results for other graph
classes, specifically those defined by forbidden minors. The method might also
be of independent interest for its conceptual simplicity. Furthermore, it is
shown that fixed-point logic with counting is not expressive enough to capture
polynomial time on the classes of chordal graphs or incomparability graphs.
