CG:SHOP 2022

Minimum Partition into Plane Subgraphs

We are happy to announce the Fourth Computational Geometry Challenge, as part of CG Week in Berlin, Germany, June 6-10, 2022.

As in previous years, the objective will be to compute good solutions to instances of a difficult geometric optimization problem. The specific problem chosen for the 2022 Challenge is Minimum Plane Partition, as follows.

Description

Given a geometric graph $G=(V,E)$, with vertices represented by points in the plane, and edges by straight-line connections between vertices.

The task is to partition $E$ into as few subsets $E_1,\ldots, E_k$ as possible, such that each subgraph $G_i=(V,E_i)$ is plane: In the given geometric representation, line segments representing edges may touch at end points if and only if the corresponding edges are incident in $G_i$; no edges may cross, i.e., share points that are not segment end points.

Objective

Minimize the partition size $k$.

Motivation

The problem is related to a variety of classic problems, ranging from coloring and graph partitioning to extremal graph theory. For example, edge coloring in planar graphs H (for which it is a long-standing conjecture [2] that it is NP-hard for graphs of maximum degree Δ=4 or 5 to decide whether they have an edge coloring with Δ colors) is a special case: From a straight-line drawing of H, slightly extend all line segments, so that they cross at the vertices of H, and nowhere else.

The related problem of partitioning a geometric graph into a minimum number of plane spanning trees has received considerable attention; see Aichholzer et al. [1] for an overview.

Details of the competition (such as benchmark instances, data formats, and rules for submission and evaluation) will be announced in coming weeks.

The contributors with the most outstanding solutions will be recognized at CG Week and invited to present their results, both at the event and in the proceedings.

We are looking forward to your contributions and welcome questions and comments!

Instances

The competition consists of 225 instances with up to 75k segments; see the download button at the top. Based on your feedback for the test instances, we limited the size to 75k; this ensures that the full intersections graphs can still be computed by medium-range workstations; we also removed the meta data to make them uniform. It took a considerable effort to balance difficulty (we want challenging instances that are not easily solved by standard software) and system requirements (we want everyone to have a fair shot, regardless of available hardware). If you run into difficulties, please keep that in mind; hopefully, the result is a challenge that is suitable both for senior researchers and for students. (Comments are always welcome!)

Credit

This problem was suggested by Johannes Obenaus, FU Berlin.

References

[1] Oswin Aichholzer, Thomas Hackl, Matias Korman, Marc van Kreveld, Maarten Löffler, Alexander Pilz, Bettina Speckmann, Emo Welzl. Packing plane spanning trees and paths in complete geometric graphs Information Processing Letters, Volume 124, August 2017, Pages 35-41; full version available at https://arxiv.org/abs/1707.05440.

[2] Marek Chrobak, Takao Nishizeki. Improved edge-coloring algorithms for planar graphs. Journal of Algorithms, Volume 11, Issue 1, March 1990, Pages 102-116.

Challenge Team

Sándor Fekete, Phillip Keldenich, Dominik Krupke, Stefan Schirra

Advisory Board

Bill Cook, Andreas Fabri, Michael Kerber, Philipp Kindermann, Joe Mitchell, Kevin Verbeek

Timeline

A first batch of test instances will be released in the summer 2021; the actual benchmark instances for the Challenge will be released in the fall. The contest will close in early 2022.

• First test instances: By August 19, 2021
• Contest instances: September 19, 2021
• Contest Closes: January 19, 2022