Muhammad Jawaherul Alam
Research Interests
Graph Drawing, Graph Algorithms, Computational Geometry, Information Visualization
Research Supervisors
Ph.D. Supervisor
Dr. Stephen G. Kobourov
Associate Professor
Department of Computer Science
University of Arizona
Homepage: http://www.cs.arizona.edu/~kobourov/
B.Sc. and M.Sc. Thesis Supervisor:
Dr. Md. Saidur Rahman
Professor
Department of Computer Science and Engineering
Bangladesh University of Engineering and Technology
Homepage: http://teacher.buet.ac.bd/saidurrahman/
Research Topics
-
Contact Representations of Graphs in 2D and 3D
In a contact representation of a graph, each vertex is represented by a simple polygon on the plane or a polyhedra in 3D and each edge is represented by a non-trivial contact (common boundary with non-zero length or area). In the weighted version of the problem, the input is not only a graph but also a weight function w that assigns a weight to each vertex v of the graph and we want to realize this weight by the area of the polygon or the volume of the polyhedron representing the vertex. Such representations have practical applications in cartography, VLSI Layout, and floor-planning.
I study both weighted and unweighted variant of the problem in 2D and 3D for planar and some nonplanar graphs. Additionally I also study contact representation with other objects such as circular arcs, disks etc.
Recently I am also studying contact representation in both 2D and 3D with minimum number of building blocks (i.e., using minimum number of grid cells or "ink" in 2D and 3D).
-
Comparison of Cartogram Algorithms
A cartogram is a thematic map where a plane geographic map is distorted so that the areas of the regions in the map realize some geo-statistical data like GDP, population etc. I study various cartogram algorithms and their effectiveness in visualizing the underlying maps as well as the statistical data. See here for more details.
-
Book Embedding of Graphs
A book embedding of a graph G is a drawing of G on a "book", where the vertices are placed on a single line, called the spine of the book and the edges are drawn on a set of half-planes, called the pages of the book, such that the drawing on each page is crossing-free. Every planar graph has a book embedding on four pages. I am currently studying the book-embeddings of 1-planar graphs.
-
Threshold Coloring
Given a graph G=(V,E) and a partition of the edges in E into "near" and "far" edges, a threshold coloring of G assigns colors to the vertices in V such that for all near (far) edges (u,v) the difference between the colors for u and v is smaller (greater) than a "threshold".
Play a fun game based on this problem here.
-
Straight-Line Grid Drawings
In a straight-line grid drawing, the vertices of a graph are placed on integer grid points and the edges are drawn with straight-line segments. The goal is to draw a graph on a small grid area. Additionally for planar and 1-planar graphs, it is desired to find a planar or 1-planar drawing of the graph respectively.
-
Fitting Graphs on Maps
Here a planar graph with a partitioning of its vertices into clusters and a plane map (with a one-to-one correspondence between the clusters in the graph and the regions in the map) are given. The graph is drawn on top of the map so that the clusters of vertices are placed in pre-specified regions of the map.
-
Smooth Orthogonal Drawings of Graphs
In a smooth orthogonal drawing of a graph, each edge is drawn with a smooth orthogonal curve: a sequence of circular arcs such that any two consecutive arcs share a common orthogonal tangent at their common point. The goal is minimize the number of arcs required for each edges. to find a
-
Layered Drawings of Planar Graphs
A Layered Drawing of a planar graph is a straight-line drawing of the graph, where the vertices are placed a set of horizontal lines, called layers. Practical applications in various fields, such as Information Visualization and VLSI floorplanning, it is desirable to draw a planar graph on minimum number of layers.
Other Research Experiences
Summer Research
- Summer Research with Dr. David Eppstein and Dr. Michael Goodrich at University of California, Irvine in June 2014
- Summer Research with Dr. Michael Kaufmann at Universität Tübingen in July 2012 and May 2013
- Summer Research with Dr. Stefan Felsner at Technische Universität Berlin in June-July 2011
Summer Schools and Workshops
-
Bertinoro Workshop on Graph Drawing
held at University Residential Center, Bertinoro, Italy on March 9-14, 2014
Organizers: Dr. Walter Didimo and Dr. Giuseppe Liotta -
Joint Mathematics Meeting
organized by AMS in San Diego on January 9-12, 2013. -
MRC Workshop on Discrete and Computational Geometry
Held at Snowbird Resort, Utah on June 10-16, 2012.
Organizers: Dr. Satyan Devadoss, Dr. Vida Dujmovic, Dr. Joseph O'Rourke, and Dr. Yusu Wang -
Dagstuhl-Seminar 12261: Putting Data on the Map
held at Schloss Dagstuhl, Germany on June 24-29, 2012.
Organizers: Dr. Stephen G. Kobourov, Dr. Frank van Ham and Dr. Alexander Wolff -
Dagstuhl-Seminar 11191: Graph Drawing with Algorithm Engineering Methods
held at Schloss Dagstuhl, Germany on May 8-13, 2011.
Organizers: Dr. Camil Demetrescu, Dr. Michael Kaufmann, Dr. Stephen G. Kobourov and Dr. Petra Mutzel. -
JAIST Summer School on Computational Geometry and Graphs
Held at the Hakusan seminar House, Japan on July 27-31, 2009.
Lectured by: Dr. Tetsuo Asnao, Dr. Jack Snoeyink, Dr. Sergey Bereg, Dr. Ryuhei Uehara and Dr. Steven Langerman
Conference Referee
Served as external reviewer in SIAM Journal of Computing (SiComp), PLOS One, Symposium on Computational Geometry (SoCG), Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), International Symposium on Graph Drawing (GD), International Colloquium on Automata, Languages and Programming (ICALP), International Workshop on Algorithms and Computations (WALCOM)