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 delta =4 or 5 to decide whether they have an edge coloring with
delta 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
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
