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

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

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.

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

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.

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

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

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

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.

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.

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.

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.

Straight Line Drawing Plane chart

Straight Line Drawing Straight line drawing Plane diagram

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

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 .

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 .

Convex drawing

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

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

Grid Drawing

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.

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.

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

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.

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.

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.

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

VLSI Layout

VLSI Floorplanning B A F E C G D Interconnection diagram

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

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

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

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

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

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

Rectangular Drawings Plane chart G of Input

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

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

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.

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.

Not each plane diagram has a rectangular drawing.

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

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.

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

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

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

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

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

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

Applications Entity-relationship outlines Flow graphs

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

A planar diagram non - planar chart planar chart

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 ・・・・

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

Thank You .:ts