  It was recently shown \cite{STV} that satisfiability is polynomially solvable
when the incidence graph is an interval bipartite graph (an interval graph
turned into a bipartite graph by omitting all edges within each partite set).
Here we relax this condition in several directions: First, we show that it
holds for $k$-interval bigraphs, bipartite graphs which can be converted to
interval bipartite graphs by adding to each node of one side at most $k$ edges;
the same result holds for the counting and the weighted maximization version of
satisfiability. Second, given two linear orders, one for the variables and one
for the clauses, we show how to find, in polynomial time, the smallest $k$ such
that there is a $k$-interval bigraph compatible with these two orders. On the
negative side we prove that, barring complexity collapses, no such extensions
are possible for CSPs more general than satisfiability. We also show
NP-hardness of recognizing 1-interval bigraphs.
