CHARACTERIZATION FOR GRAPHS WITHOUT INTERIOR VERTICES HAVING RECTANGULAR DUALS

Sitanayah, LANNY and Watuna, Noldi and Patabang, Simon (2004) CHARACTERIZATION FOR GRAPHS WITHOUT INTERIOR VERTICES HAVING RECTANGULAR DUALS. Skripsi thesis, UNIVERSITAS KATOLIK DE LA SALLE.

	PDF COVER-DAFTAR_ISI_lannySitanayah.pdf Download (480kB)
	PDF BAB_ISI-LAMPIRAN_lannySitanayah.pdf Restricted to Repository staff only Download (1MB)

Official URL: http://digilib.unikadelasalle.ac.id/

Abstract

VLSI physical design is one of the most popular applications of graph theory, in which rectangular drawing is used for VLSI floorplanning. Floorplanning is the process of placement flexible blocks, where circuits or functional modules can be represented by vertices of the graph and the adjacencies between modules can be represented by edges. The floorplan can be obtained by converting this graph into its rectangular dual.
A plane graph is a planar graph that is drawn/embedded in the plane with no two edges cross. A rectangular drawing of a plane graph G is a drawing of G in which each vertex is drawn as a point, each edge is drawn as a horizontal or vertical line segment without edge crossings, and each face is drawn as a rectangle. A rectangular dual of an n-vertex graph, G = (V, E), is comprised of n non-overlapping rectangles with the following properties: (a) Each vertex i ∈ V, corresponds to a distinct rectangle i in the rectangular dual; (b) If (i, j) is an edge in E, then rectangles i and j are adjacent in the rectangular dual. Rectangular dual deals with rectangles, which in fact consist of vertices and horizontal-vertical edges, so basically rectangular dual is rectangular drawing.
Some algorithms to find the rectangular dual of a plane graph have been proposed by using Proper Triangular Planar (PTP) graph. A PTP graph is a connected planar graph that satisfies the following properties: (a) Every face (except the exterior) is a triangle (i.e., bounded by three edges); (b) All internal
vertices have degree ≥ 4; (c) All cycles that are not faces have length ≥ 4. The
PTP graph has rectangular dual.
In this thesis we establish a necessary and sufficient condition as characteristics for a plane graph without interior vertices having rectangular dual. As a result, we obtain Proper Quadtri Exterior Plane (PQEP) graph. The PQEP graph G is a plane graph without interior vertices, which all vertices of G have degree > 1 and satisfies the following three conditions: (a) G has no more than four exterior vertices of degree 2; (b) All interior faces of G are triangles or quadrangles; (c) Interior quadrangle face of G does not contain cut-vertex. PQEP graphs have rectangular duals.

Keywords: Graph, Plane Graph, Rectangular Dual, Proper Quadtri Exterior
Plane, Floorplanning.

Item Type:

Thesis (Skripsi)

Creators: