Efficient Reassembling of Three-Regular Planar Graphs

Assaf Kfoury∗ Boston University Boston, Massachusetts kfoury at bu dot edu

Ben Sisson∗ Boston University Boston, Massachusetts bmsisson at bu dot edu

Examples

The following are some examples of reassemblies generated by the KS algorithm through the Python package

Key

Grey dashed edges have not yet been collapsed or merged.
When a vertex is added to the reassembly for the first time, it is highlighted in bold. Entire super vertices also have all of their original vertices bolded once the super vertex is first formed through a collapse or a merge.
In subsequent steps, the already collapsed and merged edges stay in non-bold black.
The red dashed edges represent the edge boundaries of a particular super vertex.
Finally, note that cycles are directed clockwise while inter-cycle trees remain undirected.

Example 1:

Step Back	Step Forward
Play animation	Restart animation

Example 2:

Step Back	Step Forward
Play animation	Restart animation

Example 3:

Step Back	Step Forward
Play animation	Restart animation

Example 4:

Step Back	Step Forward
Play animation	Restart animation

Example 5:

Step Back	Step Forward
Play animation	Restart animation

Read the paper on arXiv

Find the source on GitHub

---

∗Partially supported by NSF awards CCF-0820138 and CNS-1135722.