Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky Model

Thomas Bläsius, Guido Brückner, Ignaz Rutter

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…