Animating Planarity in Basic Algorithms

by Jaya Paliwal

A Brief Description...

Graphs can be visualized as a set of vertices that can be connected by edges. Graph theory concerns the various properties of these "graphs." For my summer research project, I have been focusing on one aspect of graph theory, planarity. Planarity is the study of planar embeddings within a graph. A graph is planar if there are no edge crossings within the graph. As graphs become larger and more complex, algorithms must be used to be able to visualize and prove that a graph is in fact planar. I am presently researching the steps of the algorithms and understanding them so that I can eventually write code that allows you to visualize the steps of the planarity algorithms and then tells you whether the graph is planar or not and why. I have been studying graphs using the software system, LINK.

GOAL:

  • Understand and teach planarity algorithm
  • To be able to animate the planarity algorithm on LINK I spent the first month of my research at Elon College in North Carolina, working with Dr.Jon Berry. Dr. Berry is a Computer Science assistant professor at Elon College and is presently projectleader of LINK. We mastered the LINK tutorial to prepare for the Reconnect and DREI confereneces taking place in July '98. After the first week, I began my research project. I am still working on my project at DIMACS,Rutgers University as well as assisting the Reconnect participants with the LINK software system. I plan to continue my research indefinitely.

    Rutgers University '01
    Douglass College

    Jaya Paliwal
    jpaliwal@dimacs.rutgers.edu