News Detail
12:04 p.m.
Dear colleagues,
We are happy to announce the Fourth Geometric Optimization Challenge, as part of CG Week in Berlin, Germany, June 710, 2022.
See https://cgshop.ibr.cs.tubs.de/competition/cgshop2022/#problemdescription
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 straightline 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 longstanding conjecture [2] that it is NPhard for graphs of maximum degree Δ=4 or 5 to decide whether they have an edge coloring with Δ colors) is a special case: From a straightline 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 edgecoloring algorithms for planar graphs. Journal of Algorithms, Volume 11, Issue 1, March 1990, Pages 102116.
[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 3541; full version available at https://arxiv.org/abs/1707.05440