  We introduce two-crossing elections as a generalization of single-crossing
elections, showing a number of new results. First, we show that two-crossing
elections can be recognized in polynomial time, by reduction to the
well-studied consecutive ones problem. We also conjecture that recognizing
$k$-crossing elections is NP-complete in general, providing evidence by
relating to a problem similar to consecutive ones proven to be hard in the
literature. Single-crossing elections exhibit a transitive majority relation,
from which many important results follow. On the other hand, we show that the
classical Debord-McGarvey theorem can still be proven two-crossing, implying
that any weighted majority tournament is inducible by a two-crossing election.
This shows that many voting rules are NP-hard under two-crossing elections,
including Kemeny and Slater. This is in contrast to the single-crossing case
and outlines an important complexity boundary between single- and two-crossing.
Subsequently, we show that for two-crossing elections the Young scores of all
candidates can be computed in polynomial time, by formulating a totally
unimodular linear program. Finally, we consider the Chamberlin-Courant rule
with arbitrary disutilities and show that a winning committee can be computed
in polynomial time, using an approach based on dynamic programming.
