Research Areas

Major research fields in which the unit currently involved in are 

Graph Drawing Algorithms

Information Visualization

VLSI Layout Algorithms

Internet Routing Protocols

Bioinformatics

Enumeration and Generating Problems
 Software Visualization and Restructuring

In the coming years, our Graph Drawing Research Group expects to perform extensive research works and extend our previous results on the following issues. 


Monotone Drawings of Graphs


A path P in a straightline drawing of a graph is monotone if there exists a line l such that the orthogonal projections of the vertices of P on l appear along l in the order induced by P. A straightline drawing of a graph is monotone if it contains at least one monotone path between every pair of vertices. Recently monotone drawings of graphs have been discovered as a new standard for visualizing graphs. Some known results on monotone drawings are given bellow.

Any strictly convex drawing of a planar graph is monotone and a monotone path from s to t can be found in O(n log n) time from strictly convex drawing of G.

Every biconnected planar graph has a straightline monotone drawing in real coordinate space.

Every tree admits a straightline planar monotone drawing on O(n)×O(n^2) or O(n^1.6)×O(n^1.6) area.

Every connected plane graph admits a monotone grid drawing on O(n) × O(n^2) grid using at most two bends per edges.

An outerplane graph of nvertices admits a straightline monotone drawing on a grid of area O(n) × O(n^2).

Not every plane graph (with fixed embedding) admits a straightline monotone drawing.

Every connected seriesparallel graph admints monotone drawing on O(n) × O(n^2) grid (submitted)
We are working on the following open problems
 Given a graph G and an integer k ∈ {0, 1}, what is the complexity of deciding whether there exists an embedding φ such that G_φ admits a monotone drawing with curve complexity k?
 Is it possible to characterize the embedded planar graphs that admit monotone drawings with curve complexity smaller than 2?






Software Visualization and Restructuring


The primary reason why maintenance is by far the most expensive phase of a software's development life cycle (60% of total cost) is because of the prevalence of bad designs in code, which decrease the readability, understandibility and maintainability of the code. Software restructuring has thus become a crucial activity in the industry. Among the most important measures of software quality is cohesion. There have been many software restructuring techniques based on hierarchical agglomerative clustering (HAC) algorithms that restructure large modules with low cohesion into smaller modules with high cohesion. These techniques generate clustering trees (or dendrograms) of the modules. The clustering trees are then sliced at different cutpoints to obtain the desired restructurings. Choosing the appropriate cutpoints is a difficult problem in clustering. Recent techniques such as SLINK, CLINK, WPGMA, and AKNN generate dendrograms which have a large number of cutpoints, which return clusters of which only a few lead to a meaningful restructuring. Our goal is to design hierarchical clustering algorithms that exploit graph decompostion algorithms in order to generate dendrograms that are easier to use, i.e., which have a lesser number of cutpoints and fewer bad clusters, of software at different levels (e.g., function, class, package, and architechurelevel).






Drawing Graphs in linear area 

The most typical and widely studied drawing style is the "straightline drawing'' of a planar graph. A straightline drawing of a planar graph G is a drawing of G such that each vertex is drawn as a point and each edge is drawn as a straightline segment without edge crossings. A straightline grid drawing of a planar graph G is a straightline drawing of G on an integer grid such that each vertex is drawn as a grid point. Although trees, a sub class of planar graphs admit straightline grid drawings with linear area, it is generally thought that triangulations may require a grid of quadratic size. Hence finding nontrivial classes of planar graphs richer than trees that admit straightline grid drawings with quadratic area is posted still an open problem. Regarding lineararea drawing algorithms for planar graphs, our goal is to find new classes of planar graphs which admit straightline grid drawing on a grid of linear area.




Top5


Planar Drawings with minimum number of line segments representing the edges 

A "straight line drawing" of a planar graph G is a drawing of G where each vertex is drawn as a point and each edge is drawn as a straight line segment. One of the important aesthetic criteria for the straight line drawing is to minimize the number of maximum straight line segments required for the straight line drawing. A "minimum segment drawing" of a planar graph G is a straight line drawing of G with the minimum number of maximal straight line segments. In this problem we want to study the problem of finding minimum segment drawings of different classes of planar graphs particularly trees and outerplanar graphs. Finding a polynomial time algorithm to compute an outer planar drawing of a given outer planar graph with the minimum number of segments is an open problem. With the aim to solving this open problem we have started our research work and hope to find a lineartime algorithm for computing a minimum segment drawing of a subclass of outer planar graphs. In near future we would like to generalize our result for general outer planar graphs.




Top5


Proximity Drawings 

A proximity drawing of a plane graph G is a straightline drawing of G with the additional geometric constraint that two vertices of G are adjacent if and only if the welldefined "proximity region'' of these two vertices does not contain any other vertex. This geometric constraint is also known as the "proximity constraint''. In one class of proximity drawings, known as betadrawings, the proximity region is parameterized by β, where 0≤β<∞. One of the open problems is to extend the problem of βdrawability of graphs to other nontrivial classes of graphs apart from trees and outer planar graphs. In our group, we plan to focus on the proximity drawability problem for more general classes of graphs like kouterplane graphs or seriesparallel graphs.




Top5


Upward and QuasiUpward Planar Drawing 

In an upward planar drawing of a digraph, every vertex is mapped to a point in the Euclidean plane and every edge is drawn as a simple curve monotone in the vertical direction without producing any crossing with other edges. The problem can be studied both in the fixed embedding setting and in the variable embedding setting. In our group, we plan to develop polynomial time upward planarity testing algorithms for other special classes of digraphs.




Top5


Planar Drawings in the minimum number of Layers 

A klines drawing of a graph G is a planar straightline grid drawing of G where each vertex of G is mapped to a grid point located on one of k horizontal lines in the Euclidean plane. In our group, we plan to study the klines drawing problem for trees using the minimum number of layers


Top5


Orthogonal Drawings 

An orthogonal drawing of a planar graph is a drawing of the graph where each vertex is drawn as a point and each edge is drawn as a sequence of alternate horizontal and vertical line segments without edge crossing. Orthogonal drawings of planar graphs have many practical applications in software engineering, VLSI circuit design, etc. Most of the known algorithms for orthogonal drawing deal with some specific classes of graphs. Our plan is to develop an orthogonal drawing framework for drawing large graphs representing internet, telecommunication network etc. 

Top5


Development of Visualization Software 

Our group aims at developing a complete visualization software that will extensively deploy graph drawing algorithms for various application areas. In this regard, our plans for the next few years is as follows.



Develop an Objectoriented Design for the software

Develop software class diagrams

Develop auxiliary algorithms, e.g., algorithms for canonical decomposition, st numbering, augmentation to yield a biconnected subgraph, planarization, canonical ordering and Schnyder labeling etc.

Develop graph generators which will randomly generate planar biconnected and triconnected graphs, trees, st digraphs etc.

Develop generic algorithms capable of producing final drawings from layouts computed by specific graph drawing algorithms.

Study and use GraphML with a view to increasing interoperability with other graph drawing tools and accessing benchmark data.




Top5
