EulerTikz
Project Overview
EulerTikz is an implementation of graph drawing algorithms in Python3, with rendering in matplotlib. Currently, EulerTikz includes an implementation the force-based layout algorithm for simple connected undirected unlabelled graphs.
Utilities
The dependencies include:
- Python 3.x.x
- Numpy
- matplotlib
How to use
- Run
python3 main.py
- Input graph in the format
<number of vertices> <number of edges>
<vertex> <vertex>
.
.
.
<vertex> <vertex>
where each pair of vertex labels preceding the first line denotes an edge.
Force-based layout
Force-based layout algorithm simulates the idea of a physical system of attractive spring forces along edges and repulsive forces caused due to the vertices. Given a simple undirected graph
Running time analysis
Let
Advantages
- simple to understand
- can detect symmetric representations
Disadvantages
- not always optimal, cannot draw trees well
- does not necessarily minimize crossing number, for instance
$Q_{3}$ - some graphs may require a large number of iterations to find a solution, hence the algorithm can practically be slow
Examples
Issues
- Modify force-based layout to draw any simple undirected graph by simply detecting components and ensuring components do not coincide with other components of the graph
- Implement spectral layout algorithm