Rifat planar bring bipartite G

 Rifat planar draw bipartite G Essay

PLANAR DRAWINGS OF BIPARTITE GRAPHS BY

GETTING RID OF MINIMUM RANGE OF EDGES

MUHAMMAD OARISUL HASAN RIFAT

Office of Computer system Science and Engineering

Chittagong University of Engineering & Technology (CUET),

Chittagong-4349, Bangladesh.

PLANAR DRAWINGS OF BIPARTITE GRAPHS SIMPLY BY

ELIMINATING BARE MINIMUM NUMBER OF CORNERS

A thesis is published in incomplete fulfillment from the requirements to get the degree of Research in Pc Science and Engineering.

By simply

Muhammad Oarisul Hasan Rifat

(0404054)

Closely watched by

A H Meters Ashfak Habib

Assistant Professor, Dept. of CSE

CUET, Bangladesh.

Section of Pc Science and Engineering

Chittagong University of Engineering & Technology (CUET),

Chittagong-4349, Bangladesh.

The thesis titled Planar Drawings of Bipartite Chart by Eliminating Lowest Number of Corners submitted simply by Roll Zero: 0404054 Program 2007-2008 continues to be accepted while satisfactory in fulfillment of the requirement for the level of Bachelor of Science in Computer Science and Engineering(B. Sc. Engg) in Chittagong University of Engineering and Technology.

Board of Examiners

1 .

A H Meters Ashfak Habib

Chairman

Assistant Professor,

Department of Laptop Science and Engineering (CSE)

Chittagong University of Anatomist and Technology (CUET)

Chittagong 4349, Bangladesh.

2 .

Prof. Dr . Md. Tazul Islam

Member

Office of Laptop Science and Engineering (CSE)

(Ex-officio)

Chittagong University of Engineering and Technology (CUET)

Chittagong 4349, Bangladesh.

a few.

iii

Candidate's Declaration

It really is hereby reported that the material of this thesis is unique and any kind of part of it includes not been submitted in other places for the award in the event that any degree or degree or diploma.

Signature from the Supervisor

Personal unsecured of the Prospect

Date:

Date:

iv

Items

Board of Examiner

iii

Candidate's Announcement

vi

Acknowledgments

x

Abstract

xi

one particular

2

Introduction ………………………………………………………………..

1

1 . 1 Graph and Graph Pulling …………………………………………

you

1 . 2 Graph Drawing Conventions ………………………………………

2

1 ) 2 . one particular Planar Sketching …………………………………………

a couple of

1 . installment payments on your 2 Directly Line Drawing…… ……………………………

a few

1 . installment payments on your 3 Rechtwinklig Drawing …………………….. …………….

5

1 . 2 . 4 Rectangle-shaped Drawing ……………. …………………….

5

1 . installment payments on your 5 Grid Drawing ……………….. ………... ……………….

6

1 . 2 . 6 Polyline Drawing ……….. ……………………………...

6

1 ) 2 . several Visibility Sketching. …………………….. ………………

7

1 . 2 . almost eight Upward Sketching ….. …………………………………...

7

1 . 3 Sketching Aesthetics …………………………………………………

8

1 . 4 Bipartite Graph ……………………………………………………..

12

1 ) 5 Inspiration and Literary works Review……………………………….. …

13

1 . 6 Goals of this Thesis ……………………………………………

15

1 . 7 Summary ……………………………………………………………

15

Preliminaries ………………………………………………………………..

seventeen

2 . 1 Basic Terminology …………………………………………………

18

v

2 . 1 . one particular Graphs …………………………………………………

17

2 . 1 . a couple of Degree of a Vertex..... …………………………………

18

installment payments on your 1 . 3 `Subgraphs ….. …………………………………………

18

2 . 1 . 4 Linked Components…………………………………

nineteen

2 . 1 . 5 Vertex

20

…. …………………………………………...

2 . 1 . six Edge

….. ………………………………………….

twenty

2 . 1 ) 7 Forest

………………………………………………

twenty

2 . 1 ) 8 Planar Graphs ……………………………………..

21

installment payments on your 1 . on the lookout for Plane Charts …………………………………………...

22

2 . 1 ) 10 Chart Coloring …………………………………………

23

installment payments on your 1 . eleven Connectivity …………………………………………...

24

installment payments on your 2 Complete Graphs

………….. ………………………………….......

24

2 . installment payments on your 1 Homes of Finish Graph …………………………

25

2 . 2 . 2 Comparison Between Complete

Graph and Complete Bipartite Graph………………..

twenty six

2 . installment payments on your 3 Planar Drawings of Complete Charts. …………………..

26

2 . three or more Bipartite Charts …………………………………………………….

dua puluh enam

2 . several. 1 Houses of Finish Graph …………………………

27

installment payments on your 4 Difficulty of Formula ………………………………………….

twenty-seven

2 . 5. 1 Intricacy Classes: S and NP ………………………… 28 2 . 4. 2 NP-Complete Problem ………………………………….

28

installment payments on your 4. three or more Approximation Algorithm and Approximation Ratio …..

29

mire

3

Planar Drawings...

petroleum anatomist Research Paper

News