Algorithms and Area Bounds for Nonplanar Orthogonal Drawings

Fößmeier, Ulrich and Kaufmann, Michael (1998) Algorithms and Area Bounds for Nonplanar Orthogonal Drawings. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997, Rome, Italy , pp. 134-145 (Official URL: http://dx.doi.org/10.1007/3-540-63938-1_57).

Full text not available from this repository.

Abstract

We report on some extensions of the Kandinsky model: A new and highly nontrivial technique to incorporate nonplanar drawings into the Kandinsky model in the same way as in the GIOTTO approach is presented. This means a major step towards the practical usability of our approach. The used technique even gives new insights for the solvability of network flow problems. Another variant of Kandinsky ensures a minimal size of the vertices removing the requirement of uniform size of each vertex. We present a new technique to evaluate our approach with the respect to the area and the number of bends, and to perform a reasonable comparison with the GIOTTO approach.

Item Type:Conference Paper
Additional Information:10.1007/3-540-63938-1_57
Classifications:G Algorithms and Complexity > G.070 Area / Edge Length
G Algorithms and Complexity > G.840 Planarization
G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
ID Code:74

Repository Staff Only: item control page

References

Bertolazzi, P., G. Di Battista, W. Didimo, Computing Orthogonal Drawings with the Minimum Number of Bends, Proc. of WADS'97, to appear.

Biedl, T.C., Orthogonal Graph Drawing, Algorithms and Lower Bounds, Diplomarbeit TU Berlin, 1995.

Biedl, T.C., M. Kaufmann, Area-Efficient Static and Incremental Drawings of High-Degree Graphs, to appear in ESA 1997.

Di Battista, G., P. Eades, R. Tamassia, I.G. Tollis, Algorithms for Drawing Graphs: An Annotated Bibliography, Computational Geometry: Theory & Applications, 235-282, 1994.

Di Battista, G., A. Garg, G. Liotta, R. Tamassia, E. Tassinari, F. Vargiu, An Experimental Comparison of Three Graph Drawing Algorithms, Computational Geometry: Theory & Applications, 1996.

CPLEX optimization, Inc., Using the CPLEX Base System.

Eades, P., J. Marks, Graph-Drawing Contest Report, Proceedings on GD '94, Princeton, LNCS 894, 143-146, 1995.

Fößmeier U., M. Kaufmann, Drawing High Degree Graphs with Low Bend Numbers, Proceedings on GD '95, Passau, LNCS 1027, 254-266, 1995.

Fößmeier U., G. Kant, M. Kaufmann, 2-Visibility Drawings of Planar Graphs, Proceedings on GD '96, Berkeley, LNCS 1190, 155-168, 1996.

Garey, M.R., D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freemann and Company, New York, 1979.

Kleinschmidt, P., personal communication.

Lawler, E.L., Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976, Chapter 4.

Papakostas A., I.G. Tollis, High-degree orthogonal drawings with small grid-size and few bends. Technical report, University of Texas at Dallas, Richardson, TX 75083, December 1996.

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., G. Di Battista, C. Batini, Automatic Graph Drawing and Readability of Diagrams, IEEE Trans. Systems, Man and Cybernetics, 61-79, 1988.