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


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


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:
Example 2:
Example 3:
Example 4:
Example 5:

Read the paper on arXiv

Find the source on GitHub

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

Maintained by Ben Sisson (last updated 9/12/2018)
Created on 4/15/2018