CG:SHOP 2022
7–10 June 2022 in Berlin, Germany
We are happy to announce the Fourth Geometric Optimization Challenge, as part of CG Week in Berlin, Germany, 07.–10. June 2022.
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:
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 E1,…, Ek as possible, such that each subgraph Gi=(V,Ei) 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 Gi; 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.
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!