Bangladesh University of Engineering and Technology
Graph Drawing Research Group
Graph Drawing and Information Visualization Laboratory
Department of Computer Science and Engineering
Bangladesh University of Engineering and Technology
Graph Drawing Research Group
Graph Drawing and Information Visualization Laboratory
Department of Computer Science and Engineering
Major research fields in which the unit currently involved in are-
In the coming years, our Graph Drawing Research Group expects to perform extensive research works and extend our previous results on the following issues
A geometric representation of a graph is a representation of the graph in which the vertices and edges are represented by geometric objects. Some examples of geometric representations of graphs are visibility representations, orthogonal representations, L-shaped representations, cover contact graphs (CCG) etc. These representations have numerous applications in VLSI layout design, state diagrams, facility location problem, data flow diagrams and social network visualization. In our group, we study different geometric representations of graphs such as bar 1-visibility representations, triangle cover contact graphs (TCCG), L-shaped orthogonal representations and L-shaped point set embeddings. We give efficient algorithms to construct geometric representations for different classes of graphs.
Given a set of points, clustering problems ask to partition the points into some clusters so that an objective function is minimum. The objective function may be the sum of radii of the clusters, maximum distance between to points in a cluster etc. In addition to the objective function, many variants of clustering problems have additional constraints such as bounds on number of points in each cluster, bounds on the number of clusters etc. The geometric clustering problems have applications in locating facilities, protecting data privacy, wireless communication etc. In our group we study different variants of clustering problems such as r-gather clustering problem, l-diversity problem etc. We aim to give efficient algorithms for these problems based on theoretical foundation as well as experimental evaluation.
The facility location problem is a well known combinatorial optimization problem. GIven a set of customers C, a set of proposed facility locations F, an opening cost cost(f) of each facility f, and a connection cost between each customer c and each facility f, the facility location problem asks to set up facilities in a subset of proposed facility locations and assign customers to the facilities so that a designated cost function is minimum. Different variants of the facility location problems are well studied. In our group we study many variants of the facility location problem such as r-gathering problem, facility assignment problem, facility dispersion problem etc. We attempt to give efficient exact algorithms, competitive online algorithms for these problems in different practical settings.
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.