License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2022.71
URN: urn:nbn:de:0030-drops-160794
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16079/
Crombez, Loïc ;
da Fonseca, Guilherme D. ;
Gerard, Yan ;
Gonzalez-Lorenzo, Aldo
Shadoks Approach to Minimum Partition into Plane Subgraphs (CG Challenge)
Abstract
We explain the heuristics used by the Shadoks team to win first place in the CG:SHOP 2022 challenge that considers the minimum partition into plane subgraphs. The goal is to partition a set of segments into as few subsets as possible such that segments in the same subset do not cross each other. The challenge has given 225 instances containing between 2500 and 75000 segments. For every instance, our solution was the best among all 32 participating teams.
BibTeX - Entry
@InProceedings{crombez_et_al:LIPIcs.SoCG.2022.71,
author = {Crombez, Lo\"{i}c and da Fonseca, Guilherme D. and Gerard, Yan and Gonzalez-Lorenzo, Aldo},
title = {{Shadoks Approach to Minimum Partition into Plane Subgraphs}},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
pages = {71:1--71:8},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-227-3},
ISSN = {1868-8969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16079},
URN = {urn:nbn:de:0030-drops-160794},
doi = {10.4230/LIPIcs.SoCG.2022.71},
annote = {Keywords: Plane graphs, graph coloring, intersection graph, conflict optimizer, line segments, computational geometry}
}
