Java

TOPIC 26 – DRAWING GRAPHS

LESSON NOTE

COMPLEXITY

Drawing a graph onto screen can become very complex. First, you must distribute the vertices far away from each other. You probably want to fill the area well. Then you must draw the edges. And then, you have to consider if the edges cross in a strange way. Or perhaps the look of the graph is way more messy than it should be. So…. You restart…. J

OUR DRAWING METHODS

At current time, Mr. Campeau has implemented three simple drawing methods that make use of NOOPDraw. These methods are simple and are very capable of drawing "bad" graphs.

The hope is that over time, new methods (perhaps student solutions) will be added to the file in order to give us more options.

GENERAL STRATEGY

There is a simple general strategy used in all three drawing methods. First, each vertex is associated with a coordinate on the screen. This is the difficult step. After that is done, we simply draw all edges and all vertices based on those coordinates.

DRAWING METHOD #1 – RANDOM

This approach associates vertices with random locations on the screen. Then the graph is drawn accordingly. It works reasonably well consider such a simple approach but does generate many bad graphs.

DRAWING METHOD #2 – GRID CENTER

This approach separates the drawing area into a grid. Each cell in the grid gets a vertex at its center. This creates beautifully aligned graphs. However, this very alignment leads to confusing edges that might incorrectly pass through other vertices giving the viewer the false impression that some vertices are connected.

DRAWING METHOD #3 – GRID OFFSET

This approach again separates the drawing area into a grid but places vertices randomly inside each cell. The advantage is that the graph fills the area well and accidental collisions between edges and vertices are less common than in method #2. However, the vertices are not as nicely aligned.

DRAWING METHOD #4 – THE CIRCLE (by Evan Duhamel, 2016)

This approach involves placing all vertices along a large circle. The benefit is that no edges will accidentally pass under (or collide) with an unassociated vertex. One drawback is that there are many many crossovers of edges – something that would be avoided ideally. But is looks quite neat!