Polygon Packing Approach to Disconnected Graph Layout

Cihad Başköy

MS Thesis Presentation
Supervisor: Asst. Prof. Uğur Doğrusöz

Graph layout has become an important area of research in Computer Science for the last couple of decades.
There is a wide range of applications for graph layout including data structures, databases, software engineering,
VLSI technology, electrical engineering, production planning, chemistry, and biology. Most layout algorithms assume
the graph to be connected. However, most graphs are disconnected and a method for putting the disconnected
graph objects together is needed.
Two-dimensional bin packing problems have wide area of application such as in the steel and textile industry.
In steel industry, problems frequently occur when the need to stamp polygonal figures from a rectangular board arises.
In the textile industry, similar problems exist. The aim is same: to maximize the use of the contiguous remainder
of the board.
Recently, two-dimensional packing has also been used in disconnected graph layout yielding algorithms that ‘tile’
the disconnected graph objects, which are represented by rectangles. These algorithms are also required to respect
the specified aspect ratio for the final layout. A more recent approach to disconnected graph layout
has been the use of polyominoes for representing the graph objects resulting in more accurate packings
at the cost of increased execution times. A trade off between time-complexity and performance drawing of graph layout
in these methods always exists.
In this thesis, we use polygons for a more accurate representation of graph objects and present new algorithm
for disconnected graph layout. Specifically, we apply the No-Fit Polygon approach in two-dimensional packing
to disconnected graph layout. We present and analyze the graph layouts resulting from our new approach and contrast
the new approach with previous ones.

DATE:
January 27, 2003, Monday @ 13:40
PLACE: EA-502