/Star-Forest-Decompositions

We deal with the problem of decomposing a complete geometric graph into plane star-forests. In particular, we disprove a recent conjecture by Pach, Saghafian and Schnider by constructing for each even n a complete geometric graph on n vertices which can be decomposed into n/2+1 plane star-forests.

Primary LanguageJupyter Notebook

Abstract

We deal with the problem of decomposing a complete geometric graph into plane star-forests. In particular, we disprove a recent conjecture by Pach, Saghafian and Schnider by constructing for each even $n$ a complete geometric graph on $n$ vertices which can be decomposed into $\frac{n}{2}+1$ plane star-forests. Additionally we prove that for complete abstract graphs a decomposition into plane star-forests is composed of a matching and $\frac{n}{2}$ star-forests with 2 edge-balanced components, which we call broken double stars.

The Structure of Project

The entirety of the project was done using Google Colab, and therefore consists of multiple Jupyter Notebooks. The best way to read all of it is:

  1. file star_forests_6_points.ipynb, describing the process of finding all star-forest decompositions of 6-point sets, as well as generating pictures which describe them.
  2. file star_forests_8_points.ipynb, describing the process of finding all star-forest decompositions of 8-point sets.
  3. file star_forests_8_pics.ipynb, generating pictures of the decompostions of 8-point sets.

Notes

  1. The pre-print of the paper this data is used in will soon be published on arxiv.
  2. For transparency, we also include the file 8-5-partitions.txt, where we stored the point sets of size 8 which admit star-forest decompositions, as well as one example partition for each of them. They are also displayed in star_forests_8_pics.ipynb.
  3. As the star_forests_8_pics.ipynb file is currently too large to be displayed on github, we recommend opening it using github.dev. Here is how to do this: image