Introduction | Prepared Examples |

### 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

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.