Abstract
We present a linear time algorithm based on Schnyder trees that produces planar polyline drawings. These drawings have the optimal area (4(n-1)2/9) and width (⌊2(n-1)/3⌋), and have at most n-2 bends, where n is the number of vertices of the graph. Moreover, at most one bend per edge is needed.
This work has been supported by the TMR Research Network GETGRATS.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
C. Batini,, G. di Battista, and R. Tamassia. Automatic graph drawing and readability of diagrams. IEEE Transactions on Systems, Man, and Cybernetics, 18(1):61–79, 1988.
G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing: Algorithms for the visualisation of graphs. Prentice Hall, 1999.
G. Di Battista and R. Tamassia. Algorithms for plane representations of acyclic digraphs. In Theoret. Comput. Sci, volume 61, pages 175–198, 1988.
G. Di Battista, R. Tamassia, and I.G. Tollis. Constrained visibility representations of graphs. In Inform. Process. Lett., volume 41, pages 1–7, 1992.
N. Bonichon, B. Le Saëc, and M. Mosbah. Orthogonal drawings based on the stratification of planar graphs. Technical Report RR-1246-00, LaBRI, 2000.
N. Bonichon, B. Le Saëc, and M. Mosbah. Wagner’s theorem on realizers. In International Colloquium on Automata, Languages and Programming 2002 (ICALP’02), LNCS, to appear.
C. C. Cheng, C. A. Duncan, M. T. Goodrich, and S. G. Kobourov. Drawing planar graphs with circular arcs. In Graph Drawing (Proc. GD’ 99), volume 1731 of Lecture Notes in Computer Science, pages 117–126. Springer-Verlag, 1999.
Yi-Ting Chiang, Ching-Chi Lin, and Hsueh-I Lu. Orderly spanning trees with applications to graph encoding and graph drawing. In Proc. 12th Symp. Discrete Algorithms, pages 506–515. ACM and SIAM, 2001.
N. Chiba, T. Yamanouchi, and T. Nishizeki. Linear algorithms for convex drawings of planar graphs. Progress in Graph Theory, pages 153–173, 1984.
Richie Chih-Nan Chuang, Ashim Garg, Xin He, Ming-Yang Kao, and Hsueh-I Lu. Compact encodings of planar graphs via canonical ordering and multiple parentheses. In Proc. 25th International Colloquium on Automata, Languages, and Programming (ICALP’98), volume 1443, pages 118–129, 1998.
U. Föβmeier and M. Kaufmann. Drawing high degree graphs with low bend numbers. In F. J. Brandenburg, editor, Graph Drawing (Proc. GD’ 95), volume 1027 of Lecture Notes in Computer Science, pages 254–266. Springer-Verlag, 1996.
H. De Fraysseix, J. Pach, and J. Pollack. Small sets supporting fary embeddings of planar graphs. In 20th Annual ACM Symp. on Theory of Computing, pages 426–433, 1988.
H. De Fraysseix, J. Pach, and J. Pollack. How to draw a planar graph on a grid. Combinatorica, 10:41–51, 1990.
C. Gutwenger and P. Mutzel. Planar polyline drawings with good angular resolution. In S. Whitesides, editor, Graph Drawing (Proc. GD’ 98), volume 1547 of Lecture Notes in Computer Science, pages 167–182. Springer-Verlag, 1998.
G. Kant. Hexagonal grid drawings. In In Proc 18th Internat. Workshop Graph-Theoret. Concepts Comput. Sci, 1992.
G. Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16:4–32, 1996.
Gunnar W. Klau and Petra Mutzel. Quasi-orthogonal drawing of planar graphs. Research Report MPI-I-98-1-013, Max-Planck-Institut für Informatik, Im Stadtwald, D-66123 Saarbrücken, Germany, May 1998.
M. Chrobak and S. Nakano. Minimum-width grid drawings of plane graphs. In Graph Drawing (Proc. GD’ 94), pages 104–110, 1995.
P. Rosenstiehl and R.E. Tarjan. Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete Comput. Geom., 1:343–353, 1986.
W. Schnyder. Planar graphs and poset dimension. Order, 5:323–343, 1989.
W. Schnyder. Embedding planar graphs on the grid. Proc. 1st ACM-SIAM Symp. Discrete Algorithms, pages 138–148, 1990.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bonichon, N., Le Saëc, B., Mosbah, M. (2002). Optimal Area Algorithm for Planar Polyline Drawings. In: Goos, G., Hartmanis, J., van Leeuwen, J., Kučera, L. (eds) Graph-Theoretic Concepts in Computer Science. WG 2002. Lecture Notes in Computer Science, vol 2573. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36379-3_4
Download citation
DOI: https://doi.org/10.1007/3-540-36379-3_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00331-1
Online ISBN: 978-3-540-36379-8
eBook Packages: Springer Book Archive