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

61
lượt xem 18
download

Graph Drawing - Trees

Mô tả tài liệu

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

CÓ THỂ BẠN MUỐN DOWNLOAD