Towards area requirements for drawing hierarchically planar graphs
โ Scribed by Xuemin Lin; Peter Eades
- Book ID
- 104325344
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 240 KB
- Volume
- 292
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
โฆ Synopsis
Hierarchical graphs are an important class of graphs for modeling many real applications in software and information visualization. In this paper, we investigate area requirements for drawing hierarchically planar graphs regarding two di erent drawing standards. Firstly, we show an exponential lower bound for the area needed for straight-line drawing of hierarchically planar graphs. The lower bound holds even for s-t hierarchical graphs without transitive arcs, in contrast to the results for upward planar drawing. This motivates our investigation of another drawing standard grid visibility representation, as a relaxation of straight-line drawing. An application of the existing results from upward drawing can guarantee a quadric drawing area for grid visibility representation but does not necessarily guarantee the minimum drawing area. Motivated by this, we will present a new grid visibility drawing algorithm which is e cient and guarantees the minimum drawing area with respect to a given topological embedding. This implies that the area minimization problem is polynomial time solvable restricted to the class of graphs whose planar embeddings are unique. However, we can show that the problem of area minimization of grid visibility for hierarchically planar graphs is generally NP-hard, even restricted to s-t graphs.
๐ SIMILAR VOLUMES
A simple algorithm for drawing 3-connected planar graphs is presented. It is derived from the Fruchterman and Reingold spring embedding algorithm by deleting all repulsive forces and fixing vertices of an outer face. The algorithm is implemented in the system for manipulating discrete mathematical s
We describe a unified framework of aesthetic criteria and complexity measures for drawing planar graphs with polylines and curves. This framework includes several visual properties of such drawings, including aspect ratio, vertex resolution, edge length, edge separation, and edge curvature, as well