The applet:
This applet allows you to run the embedding algorithm on outer-planar graphs that you construct. Specifically, the input graphs are 2-connected, but they do not have to be maximal. If you input a graph that is not 2-connected, the applet will use only the block (maximal 2-connected component) that includes xmin and its clockwise neighbour on the outer face.
The graph is input in the left side of the applet, and the point set is input in the right side after the graph is finished.
Graph input:
- To add vertices to the graph, simply click in the graph area. Note that the applet does not allow three colinear lines, which explains why a vertex is not always added when you click.
- To add an edge, simply click on an existing vertex in the graph, then either click on another vertex or click somewhere else to add a new vertex as the edge's other endpoint.
- Since the graph must be planar, it is assumed that you are giving as input a planar embedding of the graph. Hence crossing edges are not allowed.
- Since the graph must be outer-planar, any vertices enclosed in the outer face are deleted when the graph is finished.
- When you finish the graph, click on the "Finish graph" button. The applet will clean up your graph and add dummy edges so that the algorithm can work with a maximal graph. Remember, the graph should now look like a triangulation of a polygon!
Point set input:
Once you finish the graph, you can input the point set. Again, three colinear lines are not allowed, so don't put your points too close together!
When the number of points in the point set matches the number of vertices in the graph, you can start running the algorithm!
Running the algorithm:
When the graph and the point set are both input, the algorithm is ready to go. The "Advance embedding" button runs one step of the algorithm, making one (r,s)-triangle. The "Finish embedding" button finishes the job.
Once the embedding is finished, you can either clear the embedding and embed the same graph in a different point set, or clear everything and start again!