Drawing Algorithms for Almost Planar Graphs

Summary

The project aims to develop graph drawing algorithms under a number of constraints related to planarity.

Supervisor(s)

Professor Peter Eades, Professor Seok-Hee Hong

Research Location

Information Technologies

Program Type

Masters/PHD

Synopsis

Graph drawing algorithms aim to produce human-readable pictures of relational data. These algorithms are used in visualization software underlying many data mining tools, in domains such as market surveillance, fraud detection, bioinformatics, software re-engineering, and counter-terrorism. Planar graph drawing algorithms have a long history both in the theoretical mathematical literature and the pragmatic visualization literature; however, the planarity constraint is very restrictive for practical applications, and this project aims to relax this constraint.

Keywords

graph algorithms, graph drawing, graph theory

Opportunity ID

The opportunity ID for this research opportunity is: 1012

Other opportunities with Professor Peter Eades

• Visual Analytics
• Geometric Algorithms
• Algorithmics for social networks
• Embeddings of graphs on arrangements of planes in three dimensions
• Embedding graphs in non-Euclidean geometries

Other opportunities with Professor Seok-Hee Hong

• Algorithms for Drawing Non-Planar Graphs in Three Dimensions
• Scalable Visual Analytics
• MultiPlane Graph Embedding (2.5D Graph Embeddability)
• Visualization and Analysis of Large and Complex Biological Networks and Social Networks
• 2.5D Graph Navigation and Interaction Techniques