A first batch of test instances is now online:
https://cgshop.ibr.cs.tu-bs.de/competition/cg-shop-2022/#instance-format
These are not the contest instances yet, but meant for training purposes,
running first tests, etc. If you encounter any problems, questions or
suggestions, please get in touch - that kind of interaction is an intended
part of this phase, so we can fine-tune the difficulty of the actual challenge.
Best wishes,
Sándor Fekete, Phillip Keldenich, Dominik Krupke, Stefan Schirra
> Am 21.07.2021 um 14:02 schrieb Sándor Fekete <s.fekete@tu-bs.de>:
>
> 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, Joe Mitchell, 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
>
> --
> You are currently subscribed to compgeom-announce.
> To unsubscribe or access the archives, go to
> https://sympa.inria.fr/sympa/info/compgeom-announce
>
>
>
>
**********************************************************
*
* 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
