Embedding Node-link Diagram (Graphs) in Arbitrary Shapes

Bachelor Thesis
Student Project
Master Thesis


Node-link Diagrams (Graphs) are efficient tools for representing relationships and have been used to represent transportation systems, biological pathways as well as social networks. Recently, these diagrams also appear in daily news and books for giving an overview of the content. Since the diagram may not always be the primary content on display, we need a novel technique to embed the diagram in a non-rectangle complex area.

Some interesting references could be found out here.


In this project, the student has to perform analysis on graph topology and implement an algorithm to embed a graph in a non-rectangle area nicely. The tasks involve the study of network topology analysis, optimal layout of the graph, and visual encoding of the graph representation. The idea can also be extended to time-dependent graphs or shapes. The primary target data of this project can be biological networks or transportation networks.


  • Knowledge of English language (source code comments and final report should be in English)
  • Knowledge of C++ and Qt is advantageous
  • Knowledge of Graph Libraries such BGL, GraphViz or Tulip is advantageous
  • Commitment to collaborate with international researchers


The project should be implemented as a standalone application.


For more information please contact Hsiang-Yun Wu.