News Detail

07/21/2021
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 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