Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs (extended abstract). (English) Zbl 1504.68161
Dehne, Frank (ed.) et al., Algorithms and data structures. 3rd workshop, WADS ’93. Montréal, Canada 11–13, 1993. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 709, 151-162 (1993).
Summary: An orthogonal drawing of a graph is a planar drawing such that all the edges are polygonal chains of horizontal and vertical segments. Finding the planar embedding of a planar graph such that its orthogonal drawing has the minimum number of bends is a fundamental open problem in graph drawing. This paper provides the first partial solution to the problem. It gives a new combinatorial characterization of orthogonal drawings based on the concept of spirality and provides a polynomial-time algorithm for series-parallel graphs and biconnected 3-planar graphs.
For the entire collection see [Zbl 0825.00122].
For the entire collection see [Zbl 0825.00122].
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
References:
| [1] | P. Bertolazzi, R.F. Cohen, G. Di Battista, R. Tamassia, and I.G. Tollis, “How to Draw a Series-Parallel Digraph,” Proc. 3rd Scandinavian Workshop on Algorithm Theory, 1992. |
| [2] | G. Di Battista and R. Tamassia “Algorithms for Plane Representations of Acyclic Digraphs,” Theoretical Computer Science, vol. 61, pp. 175-198, 1988. · Zbl 0678.68059 · doi:10.1016/0304-3975(88)90123-5 |
| [3] | G. Di Battista and R. Tamassia “Incremental Planarity Testing,” Proc. 30th IEEE Symp. on Foundations of Computer Sciene, pp. 436-441, 1989. |
| [4] | G. Di Battista and R. Tamassia “On Line Planarity Testing,” Technical Report CS-89-31, Dept. of Computer Science, Brown Univ. 1989. |
| [5] | P. Eades and R. Tamassia, “Algorithms for Automatic Graph Drawing: An Annotated Bibliography,” Technical Report CS-89-09, Dept. of Computer Science, Brown Univ. 1989. |
| [6] | S. Even “Graph Algoritms,” Computer Science Press, Potomac, MD, 1979. · Zbl 0441.68072 |
| [7] | G. Kant “A New Method for Planar Graph Drawings on a Grid,” Proc. IEEE Symp. on Foundations of Computer Science, 1992. |
| [8] | E. L. Lawler “Combinatorial Optimization: Networks and Matroids,” Holt, Rinehart and Winston, New York, Chapt. 4, 1976. · Zbl 0413.90040 |
| [9] | T. Nishizeki and N. Chiba, “Planar Graphs: Theory and Algorithms,” Annals of Discrete Mathematics 32, North-Holland, 1988. · Zbl 0647.05001 |
| [10] | J. A. Storer “On Minimal Node-Cost Planar Embeddings,” Networks, vol. 14, pp. 181-212, 1984. · Zbl 0546.94033 |
| [11] | R. Tamassia “On Embedding a Graph in the Grid with the Minimum Number of Bends,” SIAM J. Computing, vol. 16, no. 3, pp. 421-444, 1987. · Zbl 0654.68090 · doi:10.1137/0216030 |
| [12] | R. Tamassia, “Planar Orthogonal Drawings of Graphs,” Proc. IEEE Int. Symp. on Circuits and Systems, 1990. |
| [13] | R. Tamassia and I.G. Tollis “Efficient Embedding of Planar Graphs in Linear Time,” Proc. IEEE Int. Symp. on Circuits and Systems, Philadelphia, pp. 495-498, 1987. |
| [14] | R. Tamassia and I.G. Tollis “Planar Grid Embedding in Linear Time,” IEEE Trans. on Circuits and Systems, vol. CAS-36, no. 9, pp. 1230-1234, 1989. · doi:10.1109/31.34669 |
| [15] | R. Tamassia, I. G. Tollis, and J. S. Vitter “Lower Bounds and Parallel Algorithms for Planar Orthogonal Grid Drawings,” Proc. IEEE Symp. on Parallel and Distributed Processing, 1991. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
