Presentation | 1994/11/18 An Efficient Implementation of an Algorithm for Drawing Trees Kunihiko Hayashi, Sumio Masuda, Eiichi Tanaka, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | Various algorithms have been proposed for the problem of drawing rooted ordered trees.As one of them,Unno et al.presented an Ο(n^3) -time algorithm that(i)produces an initial drawing of a given tree, and then(ii)finds another drawing of less width by repeatedly moving subtrees.In this article,we show that the same drawing can be obtained more efficiently by maintaining the contours of subtrees.The time complexity of our method is Ο(n)if a natural res triction is imposed on the sizes of nodes. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Tree / Drawing / Algorithm / Complexity |
Paper # | COMP94-55 |
Date of Issue |
Conference Information | |
Committee | COMP |
---|---|
Conference Date | 1994/11/18(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Theoretical Foundations of Computing (COMP) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | An Efficient Implementation of an Algorithm for Drawing Trees |
Sub Title (in English) | |
Keyword(1) | Tree |
Keyword(2) | Drawing |
Keyword(3) | Algorithm |
Keyword(4) | Complexity |
1st Author's Name | Kunihiko Hayashi |
1st Author's Affiliation | Graduate School of Science and Engineering,Kobe University() |
2nd Author's Name | Sumio Masuda |
2nd Author's Affiliation | Faculty of Engineering,Kobe University |
3rd Author's Name | Eiichi Tanaka |
3rd Author's Affiliation | Faculty of Engineering,Kobe University |
Date | 1994/11/18 |
Paper # | COMP94-55 |
Volume (vol) | vol.94 |
Number (no) | 354 |
Page | pp.pp.- |
#Pages | 10 |
Date of Issue |