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, Passau, Germany , 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
ID Code:141

Repository Staff Only: item control page


Batini, C., E. Nardelli, and R. Tamassia, A Layout Algorithm for Data-Flow Diagrams, IEEE Trans. on Software Engineering, Vol. SE-12 (4), pp. 538-546, 1986.

Batini, C., M. Talamo, and R. Tamassia, Computer Aided Layout of Entity-Relationship Diagrams, The Journal of Systems and Software, Vol. 4, pp. 163-173, 1984.

H. K. B. Beck, H.-P. Galil, R. Henkel, and E. Sedlmayr: Chemistry in circumstellar shells, I. Chromospheric radiation fields and dust formation in optimcally thin shells of M-giants, Astron. Astrophys. 265 (1992) 626-642.

Di Battista G., P. Eades, R. Tamassia and I. G. Tollis, Algoritms for Automatic Graph Drawing: An Annotated Bibliography, Tech. Rep., Dept. of Comp. Sc., Brown Univ., 1993.

Di Battista, E. Pietrosanti, R. Tamassia and I. G. Tollis, Automatic Layout of PERT Diagrams with XPERT, Proc. IEEE Workshop on Visual Lang. (VL' 89), 171-176, 1989.

Di Battista, G., L. Vismara, Angles of Planar Triangular Graphs, Proc. of the 25th ACM Symposium on the Theory of Computing, San Diego, California, 1993.

Fößmeier, U., and M. Kaufmann, Drawing High Degree Graphs with Low Bend Numbers, Technical Report WSI-95-21, Univ. Tübingen 1995.

Garg, A. and R. Tamassia, On the Computational Complexity of Upward and Rectilinear Planarity Testing, Proc. of GD '94, Princeton, 1994.

Himsolt, M., Konzeption und Implementierung von Grapheneditoren, Doctoral Dissertation, Passau 1993.

Lengauer, Th., Combinatorial Algorithms for Integrated Circuit Layout, Teubner/Wiley & Sons, Stuttgart/Chichester, 1990.

Mutzel, P., The Maximum Planar Subgraph Problem, Doctoral Dissertation, Köln 1994.

Reiner, D., et al., A Database Designer's Workbench in Entity-Relationship Approach, ed. S. Spaccapietra, pp. 347-360, North-Holland, 1987.

Rosenstiehl, P., and R. E. Tarjan, Rectilinear planar layouts and bipolar orientations of planar graphs, Discrete and Comp. Geometry 1 (1986), pp. 343-353.

Protsko, L. B., P. G. Sorenson, J. P. Tremblay, and D. A. Schaefer, Towards the Automatic Generation of Software Diagrams, IEEE Trans. on Software Engineering, Vol. SE-17 (1), pp. 10-21, 1991.

Storer, J. A., The node cost measure for embedding graphs in the planar grid, Proc. 12th ACM Symposium on the Theory of Computing, 1980, pp. 201-210.

Tamassia, R., On Embedding a Graph in the Grid with the Minimum Number of Bends, SIAM Journal of Computing, vol. 16 no. 3, 421-444, 1987.

Tamassia, R., and I.G. Tollis, A unified approach to visibility representations of planar graphs, Discr. and Comp. Geometry 1 (1986), pp. 321-341.