Bangladesh University of Engineering and Technology

Graph Drawing Research Group


Graph Drawing and Information Visualization Laboratory
Department of Computer Science and Engineering












  Upcoming Conferences
  Contact Us

Research Areas


Major research fields in which the unit currently involved in are-
  • Graph Drawing Algorithms

  • Information Visualization

  • Complex Networks Analysis

  • Data Science

  • Algorithmic Challenges with Big Data

  • VLSI Layout Algorithms

  • Internet Routing Protocols

  • Bioinformatics

  • Enumeration and Generating Problems

  • Software Visualization and Restructuring
  • Graph Data Mining and Social Network Analysis
In the coming years, our Graph Drawing Research Group expects to perform extensive research works and extend our previous results on the following issues.
Geometric Representations of Graphs

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. 

Geometric Clustering Problems

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.

Facility Location Problems

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.

Complex Networks

Many real world systems can be modeled as graphs to find out their characteristics and features. A complex network is a graph whose topological features are non-trivial. The connection between the nodes in a complex network is neither purely regular nor purely random. Complex networks possess interesting characteristics like topological robustness, heavy-tailed power law degree distribution, random attack tolerance, preferential attachment, presence of high degree driver nodes, sparseness etc. A wide range of systems in nature and society like food web, world wide web, protein-protein interaction network, metabolic network, online social network, stock market network, banking network, humanitarian aid network, transportation network etc. can be modeled as complex networks. By controlling the formation and growth of these graphs, certain desired properties and features can be attained. In our group, we plan to develop algorithms for generating pro-active complex networks as well as analyzing various aspects of complex networks like community detection, driver nodes detection, motif detection failure threshold detection etc.

Deep Learning Based Approach for Social Network Analysis

In this project, we will focus on a research problem of detecting overlapping communities in social networks using deep-learning. This research possesses a great deal of significance both in national and individual level due to its diversified real-life applications. For example, this work will enable the government not only to get an overall idea of different communities of people from different online platforms and telecommunication networks like Facebook, Twitter, Viber, Skype, WhatsApp, cell phone networks etc., but also to detect critical persons who are involved in two communities with mutually adversarial views or beliefs. It will also help to observe the communities of interest over time. Dig into people views, grasping and controlling public sentiment, analyzing information dissemination to detect rumor propagation, fraud detection, suspicious community identification, etc., will be easier with help of this work. Moreover, a company can easily identify its communities of interest for product marketing or campaigning. This work can be directly applied to other scientific domains like biological science, ecological science, etc. This research can also be extended and can have multiple variations to serve specific goal or objective of an individual or an institution.

Pairwise Compatibility Graphs
  Let T be an edge weighted tree and let dmin, dmax be two non-negative real numbers where dmin <= dmax. A pairwise compatibility graph (PCG) of T for dmindmax is a graph G such that each vertex of G corresponds to a distinct leaf of T and two vertices are adjacent in G if and only if the weighted distance between their corresponding leaves lies within the interval [dmindmax]. A graph G is a PCG if there exist an edge weighted tree T and suitable dmindmax such that G is a PCG of T. PCGs have their application in modeling evolutionary relationship among set of organisms from biological data which is also called phylogeny. Despite having significant applications, the complete characterization of PCGs are not known yet. We aim to provide necessary and sufficient conditions for a graph to be PCG. We also study different variants of PCGs.

Monotone Drawings of Graphs


A path P in a straight-line 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 straight-line 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 below.

  • 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 straight-line monotone drawing in real coordinate space.
  • Every tree admits a straight-line 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 n-vertices admits a straight-line monotone drawing on a grid of area O(n) × O(n^2).
  • Not every plane graph (with fixed embedding) admits a straight-line monotone drawing.
  • Every connected series-parallel 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 cut-points to obtain the desired restructurings. Choosing the appropriate cut-points is a difficult problem in clustering. Recent techniques such as SLINK, CLINK, WPGMA, and A-KNN generate dendrograms which have a large number of cut-points, 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 cut-points and fewer bad clusters, of software at different levels (e.g., function-, class-, package-, and architechure-level).

Drawing Graphs in linear area

The most typical and widely studied drawing style is the "straight-line drawing'' of a planar graph. A straight-line 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 straight-line segment without edge crossings. A straight-line grid drawing of a planar graph G is a straight-line 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 straight-line 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 straight-line grid  drawings with quadratic area is posted still an open problem. Regarding linear-area drawing algorithms for planar graphs, our goal is to find new classes of planar graphs which admit straight-line grid drawing on a grid of linear area.



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 linear-time 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.



Proximity Drawings

A proximity drawing of a plane graph G is a straight-line drawing of G with the additional geometric constraint that two vertices of G are adjacent if and only if the well-defined "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 beta-drawings, 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 k-outerplane graphs or series-parallel graphs.



Upward and Quasi-Upward 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.



Planar Drawings in the minimum number of Layers

 A k-lines drawing of a graph G is a planar straight-line 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 k-lines drawing problem for trees using the minimum number of layers



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.


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 Object-oriented 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.