Drawing High Degree Graphs with Low Bend Numbers

We consider the problem of drawing plane graphs with an arbitrarily high vertex degree orthogonally into the plane such that the number of bends on the edges should be minimized.It has been known how to achieve the bend minimum without any restriction of the size of the vertices. Naturally, the vertices should be represented by uniformly small squares. In addition we might require that each face should be represented by a non-empty region. This would allow a labeling of the faces. We present an efficient algorithm which provably achieves the bend minimum following these constraints. Omitting the latter requirement we conjecture that the problem becomes NP-hard. For that case we give advices for good approximations. We demonstrate the effectiveness of our approaches giving some interesting examples