Graph Drawing - Trees

Chia sẻ: Nguyenhoang Phuonguyen | Ngày: | Loại File: PDF | Số trang:32

Thêm vào BST

Báo xấu

89
lượt xem 19
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo bằng tiếng Anh về hội họa - Graph Drawing - Trees

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Graph Drawing - Trees

Graph Drawing Tutorial Isabel F. Cruz Worcester Polytechnic Institute Roberto Tamassia Brown University Graph Drawing 0
Introduction Graph Drawing 1
Graph Drawing s models, algorithms, and systems for the visualization of graphs and networks 41 60 33 13 23 19 24 25 26 12 9 8 7 55 34 58 63 50 11 46 47 16 17 59 3 36 37 35 20 29 39 42 52 31 32 40 43 62 21 18 56 51 1 14 38 4 54 57 49 22 15 45 53 27 44 6 61 2 5 10 30 28 48 s applications to software engineering (class hierarchies), database systems (ER- diagrams), project management (PERT diagrams), knowledge representation (isa hierarchies), telecommunications (ring covers), WWW (browsing history) ... Graph Drawing 2
Drawing Conventions s general constraints on the geometric representation of vertices and edges polyline drawing bend planar straight-line drawing orthogonal drawing Graph Drawing 3
Drawing Conventions planar othogonal straight-line drawing a b c e d f g strong visibility representation f a c b d e g Graph Drawing 4
Drawing Conventions s directed acyclic graphs are usually drawn in such a way that all edges “ﬂow” in the same direction, e.g., from left to right, or from bottom to top s such upward drawings effectively visualize hierarchical relationships, such as covering digraphs of ordered sets s not every planar acyclic digraph admits a planar upward drawing Graph Drawing 5
Resolution s display devices and the human eye have ﬁnite resolution s examples of resolution rules: s integer coordinates for vertices and bends (grid drawings) s prescribed minimum distance between vertices s prescribed minimum distance between vertices and nonincident edges s prescribed minimum angle formed by consecutive incident edges (angular resolution) Graph Drawing 6
Angular Resolution • The angular resolution ρ of a straight- line drawing is the smallest angle formed by two edges incident on the same vertex • High angular resolution is desirable in visualization applications and in the design of optical communication networks. • A trivial upper bound on the angular resolution is 2π ρ ≤ ----- - d where d is the maximum vertex degree. Graph Drawing 7
Aesthetic Criteria s some drawings are better than others in conveying information on the graph s aesthetic criteria attempt to characterize readability by means of general optimization goals Examples s minimize crossings s minimize area s minimize bends (in orthogonal drawings) s minimize slopes (in polyline drawings) s maximize smallest angle s maximize display of symmetries Graph Drawing 8
Trade-Offs s in general, one cannot simultaneously optimize two aesthetic criteria min # crossings max symmetries Complexity Issues s testing planarity takes linear time s testing upward planarity is NP-hard s minimizing crossings is NP-hard s minimizing bends in planar orthogonal drawing: s NP-hard in general s polynomial time for a ﬁxed embedding Graph Drawing 9
Beyond Aesthetic Criteria Graph Drawing 10
Constraints s some readability aspects require knowledge about the semantics of the speciﬁc graph (e.g., place “most important” vertex in the middle) s constraints are provided as additional input to a graph drawing algorithm Examples s place a given vertex in the “middle” of the drawing s place a given vertex on the external boundary of the drawing s draw a subgraph with a prescribed “shape” s keep a group of vertices “close” together Graph Drawing 11
Algorithmic Approach s Layout of the graph generated according to a prespeciﬁed set of aesthetic criteria s Aesthetic criteria embodied in an algorithm as optimization goals. E.g. s minimization of crossings s minimization of area Advantages s Computational efﬁciency Disadvantages s User-deﬁned constraints are not naturally supported Extensions s A limited constraint-satisfaction capability is attainable within the algorithmic approach E.g., [Tamassia Di Battista Batini 87] Graph Drawing 12
Declarative Approach s Layout of the graph speciﬁed by a user- deﬁned set of constraints s Layout generated by the solution of a system of constraints Advantages s Expressive power Disadvantages s Some natural aesthetics (e.g., planarity) need complicated constraints to be expressed s General constraint-solving systems are computationally inefficient s Lack of a powerful language for the speciﬁcation of constraints (currently done with a detailed enumeration of facts, or with a set notation) Graph Drawing 13
Getting Started with Graph Drawing s Book on Graph Drawing by G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis, ISBN 0-13-301615-3, Prentice Hall, (available in August 1998). s Roberto Tamassia’s WWW page http://www.cs.brown.edu/people/rt/ s Tutorial on Graph Drawing by Isabel Cruz and Roberto Tamassia (about 100 pages) s Annotated Bibliography on Graph Drawing (more than 300 entries, up to 1993) by Di Battista, Eades, Tamassia, and Tollis. Computational Geometry: Theory and Applications, 4(5), 235-282 (1994). s Computational Geometry Bibliography www.cs.duke.edu/~jeffe/compgeom/biblios.html (about 8,000 BibTeX entries, including most papers on graph drawing, updated quarterly) s Proceedings of the Graph Drawing Symposium (Springer-Verlag, LNCS) s Graph Drawing Chapters in: CRC Handbook of Discrete and Computational Geometry Elsevier Manual of Computational Geometry Graph Drawing 14
Trees Graph Drawing 15
Drawings of Rooted Trees s the usual drawings of rooted trees are planar, straight-line, and upward (parents above children) s it is desirable to minimize the area and to display symmetries and isomorphic subtrees s level drawing: nodes at the same distance from the root are horizontally aligned s level drawings may require Ω(n2) area Graph Drawing 16
A Simple Level Drawing Algorithm for Binary Trees s y(v) = distance from root s x(v) = inorder rank 0 1 2 3 4 1 2 3 4 5 6 7 8 9 10 11 s level grid drawing s display of symmetries and of isomorphic subtrees s parent in between left and right child s parents not always centered on children s width = n − 1 Graph Drawing 17
A Recursive Level Drawing Algorithm for Binary Trees [Reingold Tilford 1983] s draw the left subtree s draw the right subtree s place the drawings of the subtrees at horizontal distance 2 s place the root one level above and half- way between the children s if there is only one child, place the root at horizontal distance 1 from the child Graph Drawing 18
Properties of Recursive Level Drawing Algorithm for Binary Trees s centered level drawing s “small” width s display of symmetries and of isomorphic subtrees s can be implemented to run in O(n) time s can be extended to draw general rooted trees (e.g., root is placed at the average x-coordinate of its children) Graph Drawing 19