Delta-confluent Drawings

Eppstein, David and Goodrich, Michael T. and Meng, Jeremy Yu (2006) Delta-confluent Drawings. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 165-176 (Official URL: http://dx.doi.org/10.1007/11618058_16).

Full text not available from this repository.

Abstract

We generalize the tree-confuent graphs to a broader class of graphs called delta-confluent graphs. This class of graphs and distance-hereditary graphs, a well-known class of graphs, coincide. Some results about the visualization of delta-confuent graphs are also given.

Item Type:Conference Paper
Additional Information:10.1007/11618058_16
Classifications:M Methods > M.999 Others
M Methods > M.900 Tree
P Styles > P.999 Others
P Styles > P.540 Planar
P Styles > P.300 Curved
ID Code:689

Repository Staff Only: item control page

References

S. Aziza and T. Biedl.: Hexagonal grid drawings: Algorithms and lower bounds. J. Pach, editor, Graph Drawing (Proc. GD '04), volume 3383 of Lecture Notes Comput. Sci., pages 18-24. Springer-Verlag, 2005.

H. Bandelt and H. M. Mulder.: Distance-hereditrary graphs. J. Combin. Theory Ser. B, 41:182-208, 1986.

P. Brass, E Cenek, C. A. Duncan, A. Efrat, C. Erten, D. Ismailescu, S. G. Kobourov, A. Lubiw, and J. S. B. Mitchell.: On simultaneous graph embedding. 8th Workshop on Algorithms and Data Structures, pages 243-255, 2003.

R. P. Brent and H. T. Kung.: On the area of binary tree layouts. Inform. Process. Lett., 11:521-534, 1980.

S. Bridgeman, A. Garg, and R. Tamassia.:A graph drawing and translation service on the WWW. S. C. North, editor, Drawing (Proc. GD '96), volume 1190 of Lecture Notes Comput. Sci., pages 45-52. Springer-Verlag, 1997.

T. M. Chan, M. T. Goodrich, S. R. Kosaraju, and R. Tamassia.: Optimizing area and aspect ratio in straight-line orthogonal tree drawings. S. North, editor, Graph Drawing (Proc. GD '96), volume 1190 of Lecture Notes Comput. Sci., pages 63-75. Springer-Verlag, 1997.

S. Y. Choi.: Orthogonal straight line drawing of trees. M.Sc. thesis, Dept. Comput. Sci., Univ. Brown, Providence, RI, 1999.

P. Crescenzi, G. Di Battista, and A. Piperno.:A note on optimal area algorithms for upward drawings of binary trees. Comput. Geom. Theory Appl., 2:187-200, 1992.

G. Damiand, M. Habib, and C. Paul.: A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs. Theor. Comput. Sci., 263(1-2):99-111, 2001.

M. Dickerson, D. Eppstein, M. T. Goodrich, and J. Y. Meng.: Confluent drawing: Visualizing nonplanar diagrams in a planar way. G. Liotta, editor, Graph Drawing (Proc. GD '03), volume 2912 of Lecture Notes Comput. Sci., pages 1-12. Springer-Verlag, 2004.

C. A. Duncan, D. Eppstein, and S. G. Kobourov.: The geometric thickness of low degree graphs. 20th Annual ACM-SIAM Symposium on Computational Geometry (SCG'04), pages 340-346, 2004.

P. Eades, T. Lin, and X. Lin.: Two tree drawing conventions. Internat. J. Comput. Geom. Appl., 3:133-153, 1993.

P. D. Eades.: Drawing free trees.Bulletin of the Institute for Combinatorics and its Applications, 5:10-36, 1992.

D. Eppstein, M. T. Goodrich, and J. Y. Meng.: Confluent layered drawings. J. Pach, editor, Graph Drawing (Proc. GD '04), volume 3383 of Lecture Notes Comput. Sci., pages 184-194. Springer-Verlag, 2005.

C. Erten and S. G. Kobourov.: Simultaneous embedding of a planar graph and its dual on the grid. M. Goodrich and S. Kobourov, editors, Graph Drawing (Proc. GD'02), volume 2518 of Lecture Notes Comput. Sci., pages 575-587. Springer-Verlag, 2003.

C. Erten and S. G. Kobourov.:Simultaneous embedding of planar graphs with few bends. J. Pach, editor, Graph Drawing (Proc. GD '04), volume 3383 of Lecture Notes Comput. Sci., pages 195-205. Springer-Verlag, 2005.

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

A. Garg, M. T. Goodrich, and R. Tamassia.: Area-efficient upward tree drawings. Proc. 9th Annu. ACM Sympos. Comput. Geom., pages 359-368, 1993.

A. Gregori.: Unit length embedding of binary trees on a square grid. Inform. Process. Lett., 31:167-172, 1989.

P. Hammer and F. Maffray.: Completely separable graphs. Discrete Appl. Math., 27:85-99, 1990.

P. Hui, M. Schaefer, and D. Stefankovic. Train tracks and confluent drawings. J. Pach, editor, Graph Drawing (Proc. GD '04), volume 3383 of Lecture Notes Comput. Sci., pages 318-328. Springer-Verlag, 2005.

P.J. Idicula.: Drawing trees in grids. Master's thesis, Department of Computer Science, University of Auckland, 1990.

G. Kant.: Hexagonal grid drawings. Proc. 18th Internat. Workshop Graph-Theoret. Concepts Comput. Sci., 1992.

C. E. Leiserson.: Area-efficient graph layouts (for VLSI). Proc. 21st Annu. IEEE Sympos. Found. Comput. Sci., pages 270-281, 1980.

C. E. Leiserson.: Area-efficient graph layouts (for VLSI). ACM Doctoral Dissertation Award Series. MIT Press, Cambridge, MA, 1983.

P. T. Metaxas, G. E. Pantziou, and A. Symvonis.: Parallel h-v drawings of binary trees. Proc. 5th Annu. Internat. Sympos. Algorithms Comput., volume 834 of Lecture Notes Comput. Sci., pages 487-495. Springer-Verlag, 1994.

E. Reingold and J. Tilford.: Tidier drawing of trees. IEEE Trans. Softw. Eng., SE-7(2):223-228, 1981.

K. J. Supowit and E. M. Reingold.: The complexity of drawing trees nicely. Acta Inform., 18:377-392, 1983.

J. S. Tilford.: Tree drawing algorithms. Technical Report UIUCDCS-R-81-1055, Department of Computer Science, University of Illinois at Urbana-Champaign, 1981.

L. Valiant.: Universality considerations in VLSI circuits. IEEE Trans. Comput., C-30(2):135-140, 1981.

J. Q. Walker II.: A node-positioning algorithm for general trees. Softw. - Pract. Exp., 20(7):685-705, 1990.

C. Wetherell and A. Shannon.: Tidy drawing of trees. IEEE Trans. Softw. Eng., SE-5(5):514-520, 1979.