Straight-Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs |
| |
| Authors: | Peter Eades Qingwen Feng Xuemin Lin Hiroshi Nagamochi |
| |
| Affiliation: | (1) School of Information Technologies, University of Sydney, NSW 2006, Australia;(2) National ICT, Australia;(3) School of Computer Science and Engineering, University of New SouthWales, Sydney,NSW2052, Australia;(4) Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University Yoshida Honmachi, Sakyo, Kyoto 606-8501,, Japan |
| |
| Abstract: | Hierarchical graphs and clustered graphs are useful non-classical graph models for structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. Both have applications in CASE tools, software visualization and VLSI design. Drawing algorithms for hierarchical graphs have been well investigated. However, the problem of planar straight-line representation has not been solved completely. In this paper we answer the question: does every planar hierarchical graph admit a planar straight-line hierarchical drawing? We present an algorithm that constructs such drawings in linear time. Also, we answer a basic question for clustered graphs, that is, does every planar clustered graph admit a planar straight-line drawing with clusters drawn as convex polygons? We provide a method for such drawings based on our algorithm for hierarchical graphs. |
| |
| Keywords: | Computational geometry Automatic graph drawing Hierarchical graph Clustered graph Straight-line drawing |
| 本文献已被 SpringerLink 等数据库收录！ |
|
