Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs

@article{citeulike:101929, abstract = {We describe a new approach for cluster-based drawing of large graphs, which obtains clusters by using binary space partition (BSP) trees. We also introduce a novel BSP-type decomposition, called the balanced aspect ratio (BAR) tree, which guarantees that the cells produced are convex and have bounded aspect ratios. In addition, the tree depth is O(log n), and its construction takes O(n log n) time, where n is the number of points. We show that the BAR tree can be used to recursively...}, author = {Duncan, Christian A. and Goodrich, Michael T. and Kobourov, Stephen G. }, citeulike-article-id = {101929}, journal = {Lecture Notes in Computer Science}, keywords = {hierarchy, largegraph}, pages = {111--124}, posted-at = {2005-10-18 17:41:00}, priority = {2}, title = {Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs}, url = {http://citeseer.ist.psu.edu/duncan00balanced.html}, volume = {1547}, year = {1998} }

TY - JOUR ID - citeulike:101929 L3 - citeulike-article-id:101929 TI - Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs JF - Lecture Notes in Computer Science VL - 1547 SP - 111 EP - 124 N2 - We describe a new approach for cluster-based drawing of large graphs, which obtains clusters by using binary space partition (BSP) trees. We also introduce a novel BSP-type decomposition, called the balanced aspect ratio (BAR) tree, which guarantees that the cells produced are convex and have bounded aspect ratios. In addition, the tree depth is O(log n), and its construction takes O(n log n) time, where n is the number of points. We show that the BAR tree can be used to recursively... KW - hierarchy KW - largegraph AU - Duncan, Christian AU - Goodrich, Michael AU - Kobourov, Stephen PY - 1998/// UR - http://citeseer.ist.psu.edu/duncan00balanced.html ER -