Drawing High Degree Graphs with Low Bend Numbers

Fößmeier, Ulrich and Kaufmann, Michael (1996) Drawing High Degree Graphs with Low Bend Numbers. In: Symposium on Graph Drawing, GD 1995, September 20-22, 1995 , pp. 254-266(Official URL: http://dx.doi.org/10.1007/BFb0021809).

Full text not available from this repository.


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.

Item Type: Conference Paper
Additional Information: 10.1007/BFb0021809
Classifications: G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
URI: http://gdea.informatik.uni-koeln.de/id/eprint/141

Actions (login required)

View Item View Item