Skip to content
An exploration of tree and force-directed graph drawing algorithms.
Branch: master
Clone or download
Latest commit 73707fd Jun 27, 2018
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
animations Added tree drawing via linear program May 13, 2018
lib
report
src Updated readme, some clean-up Jun 27, 2018
tests
.gitattributes
.gitignore Added report Apr 30, 2018
.gitmodules Added hypercube drawings Jun 13, 2018
CMakeLists.txt
CMakeSettings.json Added linear model of barycenter layout May 5, 2018
CppProperties.json
README.md Update README.md Jun 27, 2018
bibtex.bib
report.bbl
report.bcf
report.blg
report.pdf
report.run.xml
report.tex
tesseract.csv Added hypercube drawings Jun 13, 2018
tree-prototype.png
tree_prototype.xlsx

README.md

Dots and Lines: A Survey of Graph Drawing Algorithms

This repository contains the report and code for my senior thesis paper on graph drawing algorithms. In mathematics, graphs are a collection of nodes connected to each other by vertices. More concretely, a social network (e.g. Facebook) can be thought of a graph if nodes represent people and vertices represent friendships. Because of the importance of graphs in many fields outside math, including computer science, algorithms for the visualization of graphs have been widely studied. In my paper, I give extra attention to three selected algorithms.

  • Read the report for a detailed explication of the algorithms, and some discussion of the mathematics (including proofs)
  • For some cool animations of force directed algorithms at work, click here
  • For the C++ code behind these images, click here

And of course, for my original inspiration read this book.

C++ Information

This project was built as a series of C++11 programs pusing Microsoft Visual Studio v15.6.4 on Windows 10 using CMake. There are three main programs:

  • animate_spring.exe: A program for creating animations and static drawings of Eades' algorithm
  • animate_tutte.exe: A program for creating animations of Tutte's algorithm or static drawings using a linear algebra based solver
  • tree_lp.exe: A program for drawing (random) binary trees via a linear program

Supowit and Reingold's Tree Drawing Program

In their 1983 paper on the complexity of tree drawing, Supowit and Reingold describe a linear program for drawing binary trees. A result of this algorithm is shown below:

Force Directed Algorithms

Eades' Spring Force Directed Algorithm

This algorithm visualizes nodes as rings hooked onto steel springs (edges). In addition, there's also an electric force between vertices, so that they don't completely overlap.

Tesseract

Algorithm Trace of Eades' Algorithm for K9

Tuttes' Barycenter Algorithm

In this classic force directed algorithm, a strictly convex polygon is drawn on the exterior, with some nodes nailed down onto the vertices on this polygon. Then, the other nodes are placed in the "center of mass" of this polygon. This is an algorithm of limited utility, since it doesn't handle many nodes, and only gives aesthetically pleasing results for 3-connected graphs. However, some of the results of this algorithm are pretty slick.

Durer Graph

Cubic Symmetric Graph F048A

You can’t perform that action at this time.