1 / 58

# CSE 6405 Chart Drawing.

67 views
Category: Education / Career
Description
T. Nishizeki and M. S. Rahman, Planar Graph Drawing, World Scientific, Singapore, 2004. ... A drawing of a diagram is planar if no two edges cross in the drawing. ...
Transcripts
Slide 1

﻿8 7 5 6 4 3 2 1 CSE 6405 Graph Drawing

Slide 2

Text Books T. Nishizeki and M. S. Rahman, Planar Graph Drawing, World Scientific, Singapore, 2004. G. Di Battista, P. Eades, R. Tamassia, I. G. Tollies, Graph Drawing: Algorithms for the perception of Graphs, Prentice-Hall Inc., 1999.

Slide 3

Marks Distribution Attendance 10 Participation in Class Discussions 5 Presentation 20 Review Report/Survey Report/Slide Prepration 10 Examination 55

Slide 4

Presentation A paper (or a section of a book) from the zone of Graph Drawing will be allocated to you. You need to peruse, comprehend and display the paper. Use PowerPoint slides for presentation.

Slide 5

Presentation Format Problem definition Results of the paper Contribution of the paper in admiration to past results Algorithm and system including blueprint of the verifications Future works, open issues and your thought

Slide 6

Presentation Schedule Presentation time: 25 minutes Presentation will begin from 5 th week.

Slide 7

Graphs and Graph Drawings STATION ATM-HUB ATM-RT ATM-RT ATM-SW STATION ATM-HUB ATM-SW ATM-RT ATM-SW STATION ATM-HUB STATION ATM-SW ATM-SW STATION ATM-HUB ATM-HUB ATM-RT STATION An outline of a PC system

Slide 8

Symmetric Eades, Hong Objectives of Graph Drawings Nice drawing structure of the diagram is straightforward structure of the chart is hard to comprehend To acquire a decent representation of a diagram so that the structure of the chart is effortlessly justifiable.

Slide 9

8 7 5 6 4 3 2 1 Objectives of Graph Drawings Diagram of an electronic circuit 5 Wire intersections 7 4 8 3 1 2 not appropriate for single layered PCB reasonable for single layered PCB The drawing ought to fulfill some paradigm emerging from the application perspective.

Slide 10

Drawing Styles Planar Drawing A drawing of a chart is planar if no two edges cross in the drawing. It is desirable over locate a planar drawing of a chart if the diagram has such a drawing. Shockingly not all charts concede planar drawings. A chart which concedes a planar drawing is known as a planar diagram.

Slide 11

Polyline Drawing A polyline drawing is a drawing of a diagram in which every edge of the chart is spoken to by a polygonal chain.

Slide 12

Straight Line Drawing Plane chart

Slide 13

Straight Line Drawing Straight line drawing Plane diagram

Slide 14

Straight Line Drawing Straight line drawing Plane chart Each vertex is drawn as a point.

Slide 15

Straight Line Drawing Straight line drawing Plane diagram Each vertex is drawn as a point. Every edge is drawn as a solitary straight line fragment .

Slide 16

Every plane diagram has a straight line drawing . Wagner \'36 Fary \'48 Straight Line Drawing Polynomial-time calculation Straight line drawing Plane chart Each vertex is drawn as a point. Every edge is drawn as a solitary straight line section .

Slide 17

Convex drawing

Slide 18

Box-orthogonal Drawing Orthogonal drawing Rectangular Drawing Box-rectangular Drawing

Slide 19

A 46 F 8 G 19 B 65 E 23 I 12 J 14 H 37 K 27 D 56 C 11 Octagonal drawing

Slide 20

Grid Drawing

Slide 21

Grid Drawing When the implanting must be drawn on a raster gadget, genuine vertex organizes must be mapped to whole number lattice focuses, and there is no surety that a right installing will be gotten in the wake of adjusting. Numerous vertices might be gathered in a little locale of the drawing. Hence the installing might be untidy, and line convergences may not be recognized. One can\'t think about range necessity for two or more diverse drawings utilizing genuine number math, since any drawing can be fitted in any little zone utilizing amplification.

Slide 22

Visibility drawing A perceivability drawing of a plane diagram G is a drawing of G where every vertex is drawn as a flat line section and every edge is drawn as a vertical line portion. The vertical line fragment speaking to an edge must interface focuses on the flat line sections speaking to the end vertices.

Slide 23

A 2-perceivability drawing A 2-perceivability drawing is a speculation of a perceivability drawing where vertices are drawn as boxes and edges are drawn as either a level line section or a vertical line portion

Slide 24

Properties of chart drawing Area. A drawing is futile in the event that it is indistinguishable. On the off chance that the utilized region of the drawing is substantial, then we need to utilize numerous pages, or we should diminish determination, so whichever way the drawing gets to be mixed up. In this manner one noteworthy target is to guarantee a little region. Little drawing zone is likewise best in application areas like VLSI floorplanning. Angle Ratio. Angle ratiois characterized as the proportion of the length of the longest side to the length of the briefest side of the littlest rectangle which encases the drawing.

Slide 25

Bends. At a curve, the polyline drawing of an edge alters course, and consequently a twist on an edge builds the troubles of taking after the course of the edge. Therefore, both the aggregate number of curves and the quantity of twists per edge ought to be kept little. Intersections. Each intersection of edges bears the capability of perplexity, and accordingly the quantity of intersections ought to be kept little. State of Faces . In the event that each face has a standard shape in a drawing, the drawing looks pleasant. For VLSI floorplanning, it is attractive that every face is drawn as a rectangle.

Slide 26

Symmetry. Symmetry is a vital stylish criteria in diagram drawing. A symmetryof a two-dimensional figure is an isometry of the plane that fixes the figure. Precise Resolution. Precise determination is measured by the littlest point between nearby edges in a drawing. Higher precise determination is alluring for showing a drawing on a raster gadget.

Slide 27

Applications of Graph Drawing Floorplanning VLSI Layout Circuit Schematics Simulating atomic structures Data Mining Etc… ..

Slide 28

VLSI Layout

Slide 29

VLSI Floorplanning B A F E C G D Interconnection diagram

Slide 30

VLSI Floorplanning B An A F E C G C G D VLSI floorplan Interconnection chart

Slide 31

VLSI Floorplanning B An A F E C G C G D VLSI floorplan Interconnection diagram

Slide 32

VLSI Floorplanning B An A F E C G C G D VLSI floorplan Interconnection diagram

Slide 33

B A F E G C D VLSI Floorplanning B An A F E C G C G D VLSI floorplan Interconnection diagram Dual-like chart

Slide 34

B An A F E G C D VLSI Floorplanning B An A F E C G C G D VLSI floorplan Interconnection chart Dual-like diagram Add four corners

Slide 35

B An A F E G C D VLSI Floorplanning B An A F E Rectangular drawing E C G C G D VLSI floorplan Interconnection diagram Dual-like diagram Add four corners

Slide 36

Rectangular Drawings Plane chart G of Input

Slide 37

Rectangular Drawings corner Rectangular drawing of G Plane diagram G of Output Input

Slide 38

Rectangular Drawings corner Rectangular drawing of G Plane chart G of Output Input Each vertex is drawn as a point .

Slide 39

Rectangular Drawings corner Rectangular drawing of G Plane diagram G of Output Input Each vertex is drawn as a point. Every edge is drawn as a level or a vertical line section.

Slide 40

Rectangular Drawings corner Rectangular drawing of G Plane chart G of Output Input Each vertex is drawn as a point. Every edge is drawn as an even or a vertical line portion. Every face is drawn as a rectangle.

Slide 41

Not each plane diagram has a rectangular drawing.

Slide 42

VLSI Floorplanning B An A F E Rectangular drawing E C G C G D VLSI floorplan Interconnection diagram

Slide 43

VLSI Floorplanning B An A F E Rectangular drawing E C G C G D VLSI floorplan Interconnection chart Unwanted contiguousness Not alluring for MCM floorplanning and for some engineering floorplanning.

Slide 44

B A F A F E G C E C G D MCM Floorplanning Sherwani Architectural Floorplanning Munemoto, Katoh, Imamura Interconnection chart

Slide 45

B A F A F E G C E C G D MCM Floorplanning Architectural Floorplanning Interconnection diagram

Slide 46

B A F G E C D B A F A F E G C E C G D MCM Floorplanning Architectural Floorplanning Interconnection diagram Dual-like diagram

Slide 47

B A F G E C D B A F A F E G C E C G D MCM Floorplanning Architectural Floorplanning Interconnection chart Dual-like diagram

Slide 48

B An A F G E C D B A F A F E G C E C G D MCM Floorplanning Architectural Floorplanning Interconnection diagram Dual-like chart

Slide 49

B An A F G E C D Box-Rectangular drawing B A F A F E dead space G C E C G D MCM Floorplanning Architectural Floorplanning Interconnection chart Dual-like diagram

Slide 50

Applications Entity-relationship outlines Flow graphs

Slide 51

Applications Circuit schematics Minimization of twists lessens the quantity of "vias" or "throughholes," and henceforth diminishes VLSI manufacture costs.

Slide 52

A planar diagram non - planar chart planar chart

Slide 53

Planar diagrams and plane charts distinctive plane diagrams A plane chart is a planar chart with an altered inserting. An implanting is not settled. A planar diagram may have an exponential number of embeddings. same planar diagram ・・・・

Slide 54

Graph Drawing Data Mining Internet Computing Social Sciences Software Engineering Information Systems Homeland Security Web Searching

Slide 58

Thank You .:ts

Recommended
View more...