[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

BUBBLE TREE DRAWING ALGORITHM

  • Chapter
Computer Vision and Graphics

Part of the book series: Computational Imaging and Vision ((CIVI,volume 32))

Abstract

In this paper, we present an algorithm, called Bubble Tree, for the drawing of general rooted trees. A large variety of algorithms already exists in this field. However, the goal of this algorithm is to obtain a better drawing which makes a trade off between the angular resolution and the length of the edges. We show that the Bubble Tree drawing algorithm provides a planar drawing with at most one bend per edge in linear running time.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 158.00
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

REFERENCES

  • Amenta, N. and Klingner, J. (2002). Case study: Visualizing sets of evolutionary trees. In IEEE Infovis'02, pages 71–76.

    Google Scholar 

  • Auber, D. (2001). Tulip. In Mutzel, P., Jünger, M., and Leipert, S., editors, 9th Symp. Graph Drawing, volume 2265 of Lecture Notes in Computer Science, pages 335–337. Springer-Verlag.

    Google Scholar 

  • Auber, D. (2003). Graph Drawing Softwares, chapter Tulip- A Huge Graphs Visualization Framework, pages 80–102. Mathematics and Visualization series. Springer-Verlag.

    Google Scholar 

  • Battista, G., Eades, P., Tamassia, R., Tollis, I., and Tollis, G. (1999). Graph Drawing : Algorithms for the Visualization of Graphs. Prentice-Hall.

    Google Scholar 

  • Bruls, D. M., Huizing, C., and VanWijk, J. J. (2000). Squarified treemaps. In Data Visualization 2000, Proceedings of the joint Eurographics and IEEE TCVG Symposium on Visualization, pages 33–42. Springer.

    Google Scholar 

  • Buchheim, C., Jünger, M., and Leipert, S. (2002). Improving walker’s algorithm to run in linear time. Technical report, Zentrum für Angewandte Informatik Koln, Lehrstuhl Junger.

    Google Scholar 

  • Carriere, J. and Kazman, R. (1995). Interacting with huge hierarchies: Beyond cone trees. In G. and Eick, S., editors, IEEE Symposium on Information Visualization, pages 74–78. Atlanta, Georgia Institute for Electrical and Electronics Engineers.

    Google Scholar 

  • Eades, P. (1992). Drawing free trees. Bulletin of the Institute for Combinatorics and its Applications, 5:10–36.

    MATH  MathSciNet  Google Scholar 

  • Freund, R. M., Sun, J., and Xu, S. (2003). Solution methodologies for the smallest enclosing circle problem. Computational Optimization and Applications, 24–26.

    Google Scholar 

  • Jeon, C. S. and Pang, A. (1998). Reconfigurable disc trees for visualizing large hierarchical information space. In IEEE InfoVis’98, pages 19–25.

    Google Scholar 

  • Knuth, D. E. (1973). The Art of Computer Programming, volume 1. Addison-Wesley.

    Google Scholar 

  • Munzner, T. (1997). H3: laying out large directed graphs in 3d hyperbolic space. In IEEE Infovis'97, pages 2–10.

    Google Scholar 

  • Reingold, E. M. and Tilford, J. S. (1981). Tidier drawings of trees. IEEE Transactions on Software Engineering, 7(2):223–228.

    Google Scholar 

  • Robertson, G. G., Mackinlay, J. D., and Card, S. K. (1991). Cone trees: Animated 3d visualizations of hierarchical information. In SIGCHI, Conference on Human Factors in Computing Systems, pages 189–194. ACM.

    Google Scholar 

  • Shneiderman, B. (1991). Tree visualization with tree-maps : A 2-d space filling approach. In ACM Transaction on graphics, pages 92–99.

    Google Scholar 

  • Teoh, Soon Tee and Ma, Kwan Liu (2002). Rings: A technique for visualizing large hierarchies. In Kobourov, S. G. and Goodrich, M. T., editors, Graph Drawing, volume 2528 of Lecture Notes in Computer Science, pages 268–275. Springer.

    Google Scholar 

  • Walker, J. Q. (1990). A node positioning algorithm for general trees. Software Practice and Experience, 20:685–705.

    Google Scholar 

  • Welzl, E. (1991). Smallest enclosing disks (balls and ellipsoids). In Maurer, Hermann A., editor, New Results and New Trends in Computer Science, Lecture Notes in Computer Science, 555. Springer-Verlag.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer

About this chapter

Cite this chapter

Grivet, S., Auber, D., Domenger, J., Melancon, G. (2006). BUBBLE TREE DRAWING ALGORITHM. In: Wojciechowski, K., Smolka, B., Palus, H., Kozera, R., Skarbek, W., Noakes, L. (eds) Computer Vision and Graphics. Computational Imaging and Vision, vol 32. Springer, Dordrecht. https://doi.org/10.1007/1-4020-4179-9_91

Download citation

  • DOI: https://doi.org/10.1007/1-4020-4179-9_91

  • Publisher Name: Springer, Dordrecht

  • Print ISBN: 978-1-4020-4178-5

  • Online ISBN: 978-1-4020-4179-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics