Efficient Reassembling of Three-Regular Planar Graphs


Assaf Kfoury∗
Boston University
Boston, Massachusetts
kfoury@bu.edu

Ben Sisson∗
Boston University
Boston, Massachusetts
bmsisson@bu.edu

Abstract


        The reassembling of a simple connected graph G = (V , E) is an abstraction of a problem arising in earlier studies of network analysis. There are several equivalent definitions of graph reassembling and in this paper we use a definition which makes it closest to the notion of graph carving. The reassembling process begins with a binary tree whose leaf nodes correspond to a singleton set containing a vertex in the original graph. The parent of two nodes in the reassembly tree is defined as the union of the two child nodes' sets. The root of the binary tree is a set containing every vertex in the original graph. The edge boundary degree of a set in the reassembly of a graph is the number of edges in the original graph that connect vertices in the set to vertices not in the set. The alpha measure of a reassembly is the largest edge boundary degree of any node in the reassembly tree.
        In previous papers, graph reassembly and minimum-cutwidth linear arrangement (minimum cutwidth graph carving) were shown to be polynomial reducible to each other. In the general case, determining whether a particular graph has a carving width of at most k is an NP-complete problem. Carving widths of size k and reassemblies with alpha measures of k are also polynomial reducible to each other.
        Here, we present an algorithm that works on 3-regular biconnected planar graphs and finds a reassembly with an alpha measure of 2*p, where p is a measure similar to the outerplanarity index of the graph. For many 3-regular biconnected planar graphs, this alpha measure is optimal in the sense that no other reassemblies exist with an alpha measure less than 2*p. Additionally, this algorithm runs in linear time in terms of the number of vertices in the graph.

Read the paper on Arxiv

Find the source on GitHub


A related work of art

Matthew Sisson
matthewsissonetc@gmail.com

Algorithms


Algorithms are step by step instructions
to solve a class of problems.
They can be expressed mathematically,
in symbolic logic, or with natural language.
“Remember the Sabbath and keep it holy,”
“turn the other cheek,”
“there is no god but Allah,”
have proven sub-optimal.

A recursive algorithm
makes reference to itself until
a terminal condition is reached.
You met them in high school,
at work, and at cocktail parties.
Some become politicians, others
celebrities, all sociopathic.

Brute force, or the exhaustive search
is the naïve method of trying
every possibility until a solution is reached.
These include alcohol, drug abuse, a life of
crime, therapy and medication.

Divide and conquer needs no explanation,
especially under the present administration.

If life were like chess, I would get
on my knees and worship
Garry Kasparov or Bobby Fischer.

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