  We show that finding orthogonal grid-embeddings of plane graphs (planar with
fixed combinatorial embedding) with the minimum number of bends in the
so-called Kandinsky model (which allows vertices of degree $> 4$) is
NP-complete, thus solving a long-standing open problem. On the positive side,
we give an efficient algorithm for several restricted variants, such as graphs
of bounded branch width and a subexponential exact algorithm for general plane
graphs.
