A reassembling of a simple 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; in this report we use a definition which makes it closest to the notion of graph carving. A reassembling is a rooted binary tree whose nodes are subsets of V and whose leaf nodes are singleton sets, with each of the latter containing a distinct vertex of G. The parent of two nodes in the reassembling is the union of the two children’s vertex sets. The root node of the reassembling is the full set V . The edge-boundary degree of a node in the reassembling is the number of edges in G that connect vertices in the node’s set to vertices not in the node’s set. A reassembling’s α-measure is the largest edge-boundary degree of any node in the reassembling. A reassembling of G is α-optimal if its α-measure is the minimum among all α-measures of G’s reassemblings.
        The problem of finding an α-optimal reassembling of a simple graph in general was already shown to be NP-hard.
        In this report we present an algorithm which, given a 3-regular plane graph G = (V, E) as input, returns a reassembling of G with an α-measure independent of n = | V | and upper-bounded by 2k, where k is the edge-outerplanarity of G. (Edge-outerplanarity is distinct but closely related to the usual notion of outerplanarity; as with outerplanarity, for a fixed edge-outerplanarity k, the number n of vertices can be arbitrarily large.) Our algorithm runs in linear time O(n). Moreover, we construct a class of 3-regular plane graphs for which this α-measure is optimal, by proving that 2k is the lower bound on the α-measure of any reassembling of a graph in that class.

A related work of art

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.