๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

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


An algorithm for drawing planar graphs
โœ Bor Plestenjak ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 382 KB ๐Ÿ‘ 2 views

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

A Framework for Drawing Planar Graphs wi
โœ Michael T. Goodrich; Christopher G. Wagner ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 204 KB

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