[hpc-announce] Fourth Computational Geometry Challenge - First Announcement

[Sándor Fekete]

Dear colleagues,

We are happy to announce the Fourth Geometric Optimization Challenge, as 
part of CG Week in Berlin, Germany, June 7-10, 2022.

See https://cgshop.ibr.cs.tu-bs.de/competition/cg-shop-2022/#problem-description

As in the last year, 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 the following:

Minimum Partition into Plane Subgraphs
-----------------------------------------------------

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,…, E_k as possible, such that
each subgraph G_i=(V,E_i) is plane: In the given geometric representation,
line segments representing edges my touch at end points if and only if the 
corresponding edges are incident in G_i; no edges my cross, i.e., share
points that are not segment end points.

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 also 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; see the timeline below.

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!

Challenge Team:
----------------------
Sándor Fekete, Phillip Keldenich, Dominik Krupke, Stefan Schirra

Advisory Board:
---------------------
Bill Cook, Andreas Fabri, Michael Kerber, Philipp Kindermann, Kevin Verbeek

Timeline:
------------
- By August 19, 2020: 	Release of first test instances

- September 19, 2021: 	Contest instances, contest opens

- January 19, 2022:		Contest closes

- March 15, 2021: 		Final versions of proceedings contributions due

Credit:
---------
This problem was suggested by Johannes Obenaus, FU Berlin.

References:
----------------

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

[2]
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