Logo

Login | Create Account

Planar Polyline Drawings with Good Angular Resolution

Gutwenger, Carsten and Mutzel, Petra (1998) Planar Polyline Drawings with Good Angular Resolution. [Conference Paper]

Full text not available from this repository.

Abstract

We present a linear time algorithm that constructs a planar polyline grid drawing of any plane graph with n vertices and maximum degree d on a (2n-5) \times (3n/2-7/2) grid with at most 5n-15 bends and minimum angle >2/d. In the constructed drawings, every edge has at most three bends and length O(n). To our best knowledge, this algorithm achieves the best simultaneous bounds concerning the grid size, angular resolution, and number of bends for planar grid drawings of high-degree planar graphs. Besides the nice theoretical features, the practical drawings are aesthetically very pleasing. An implementation of our algorithm is available with the AGD-Library (Algorithms for Graph Drawing) [2,1]. Our algorithm is based on ideas by Kant for polyline grid drawings for triconnected plane graphs [23]. In particular, our algorithm significantly improves upon his bounds on the angular resolution and the grid size for non-triconnected plane graphs. In this case, Kant could show an angular resolution of 4/(3d+7) and a grid size of (2n-5) \times (3n-6), only.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.070 Area / Edge Length
M Methods > M.600 Planar
G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.540 Planar
ID Code:290
Deposited By:Arnopolina, Galina
Deposited On:09 Nov 2004
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=1547&spage=167

Repository Staff Only: item control page

References

1. AGD-Library. The AGD-Algorithms Library User Manual. Max-Planck Institut Saarbrücken, Universität Halle, Universität Köln, 1998. Available via http://www.mpi-sb.mpg.de/AGD/. Partially supported by the DFG-cluster "Effiziente Algorithmen für discrete Probleme und ihre Anwendungen".

2. D. Alberts, C. Gutwenger, p. Mutzel, and S. Näher. The design of the AGD-Algorithms Library. In G.F. Italiano and S. Orlando, editors, Proc. Workshop on Algorithm Engineering (WAE '97), Venice, Italy, September 1997.

3. T. Biedl. Optimal orthogonal drawings of connected plane graphs. In Proc. Canadian Conference Computational Geomatry (CCCG '96), vol. 5 of International Informatics Series, pages 306-311. Carleton Press, 1996.

4. T. Biedl. Orthogonal graph visualization: The three-phase mathod with applications. PhD thesis, Rutgers University, Center for Operations Research, Rutgers, 1997.

5. T. Biedl and G. Kant. A Better Heuristic for Orthogonal Graph Drawings. Comput. Geom. Theory Appl., 9:159-180, 1998.

6. T. Biedl, B. Madden, and I.G. Tollis. The three-phase method: A unified approach to orthogonal graph drawing. In DiBattista, editor, Symposium on Graph Drawing 97, vol. 1353 of LNCS. Springer-Verlag, pages 391-402, 1998.

7. F.J. Brandenburg. Nice drawings of graphs and trees are computationally hard. In Proc. of the 7th Interdisciplinary Workshop on Informatics and Psychology, vol. 439 of LNCS, pages 1-15. Springer-Verlag, 1988.

8. M. Chrobak and G. Kant. Convex grid drawings of 3-connected planar graphs. International Journal on Computational Geometry and Applications, 7(3):211-224, 1997.

9. H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10:41-51, 1990.

10. G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Algorithms for drawing graphs: An annotated bibliography. Comput. Geom. Theory Appl., 4: 235-282, 1994.

11. G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, and F. Vargiu. An experimental comparison of three graph drawing algorithms. Comput. Geom. Theory Appl., pages 7:303-326, 1997.

12. P. Eades and p. Mutzel. Graph Drawing Algorithms. CRC Handbook of Algorithms and Theory of Computation, Chapter 9, M. Atallah (ed.). CRC Press, 1998, to appear.

13. S. Fialko and P. Mutzel.A new approximation algorithm for the planar augmentation problem. In Proc. of the 9th Annu. ACM-SIAM Symposium on Discrete Algorithms (SODA '98), pages 260-269, San Francisco, CA, 1998. ACM Press.

14. U. Fößmeier and M. Kaufmann. Algorithms and area bounds for nonplanar orthogonal drawings. In G. DiBattista, editor. Symposium on Graph Drawing 97, vol. 1353 of LNCS. Springer-Verlag, pages 134-145, 1998.

15. M.R. Garey and D.S. Johnson. Crossing number is np-complete, SIAM J. Algebraic and Discrete Methods 4(1983), 312-316.

16. A. Garg. New results on drawing angle graphs. Comput. Geom. Theory Appl., 9(1/2):43-82, 1998.

17. A. Garg and R. Tamassia. On the Computational Complexity of Upward and Rectilinear Planarity Testing. Proc. DIMACS Workshop GD '94, LNCS, 894, Springer-Verlag, pages 286-297, 1994.

18. A. Garg and R. Tamassia. Planar drawings and angular resolution: Algorithms and bounds. In J. van Leeuwen, editor, Algorithms (Proc. ESA '94), volume 855 of LNCS, pages 12-23. Springer-Verlag, 1994.

19. A. Garg and R. Tamassia. A New Minimum Cost Flow Algorithm with Applications to Graph Drawing. In Proc. of the Symp. on Graph Drawing, GD'96,vol. 1190 of LNCS, pages 201-216. Springer Verlag, September 1996.

20. C. Gutwenger and P. Mutzel. Grid embeddings of biconnected planar graphs. Max-Planck-Institut für Informatik, Saarbrücken, Germany, 1997.

21. J. Hopcroft and R.E. Tarjan. Efficient planarity testing. J. ACM, 21(4):549-568, 1974.

22. C. Hundack, P. Mutzel, I. Pouchkarev, and S. Thome. ArchE: A graph drawing system for archeology. In G. Di Battista, ed., Proc. of the Symp. on Graph Drawing, GD'97, vol. 1353 of LNCS, pages 297-302. Springer Verlag, 1997.

23. Goos Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16:4-32, 1996. (Special issue on Graph Drawing, edited by G. Di Battista and R. Tamassia).

24. G.W. Klau and P. Mutzel. Quasi-orthogonal drawing of planar graphs. Technical Report MPI-I-98-1-013, Max-Planck-Institut für Informatik, Saarbrücken, Germany, 1998.

25. M.R. Kramer and J. van Leeuwen. The complexity of wire-routing and finding minimum area layouts for arbitrary VLSI circuits. Advances in Computing Research 2 (ed. F.P. Preparata), JAI Press Inc., Greenwich, CT, USA, 1984, pages 129-146.

26. P. Mutzel and S. Fialko. New approximation algorithms for planar augmentaiton. to appear, 1998.

27. H. Purchase. Which aesthetichas the greatest effect on human understanding? In G. Di Battista, ed., Proc. of the Symp. on Graph Drawing, GD'97, vol. 1353 of LNCS, pages 248-261. Springer Verlag, 1997.

28. R. Read. New methods for drawing a planar graph given the cyclic order of the edges at each vertex. Congr. Numer., 56:31-44, 1987.

29. J. Storer. On minimal node-cost planar embeddings. Network 14 (1984), pages 181-212.

30. R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16 (1987), pages 421-444.

31. R. Tamassia, G. Di Battista, and C. Batini. Automatic graph drawing and readability of diagrams. IEEE Transactions on Systems, Man and Cybernetics, SMC-18(1):61-79, 1988.

32. R. Tamassia and I.G. Tollis. Efficient Embeddings of Planar Graphs in Linear Time. IEEE Symp. on Circuits and Systems, pages 495-498, 1987.

33. R. Tamassia and I.G. Tollis. Planar grid embeddings in linear time. IEEE Trans. Circuits Syst., CAS-36(9):1230-1234, 1989.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.