Shadoks Approach to Minimum Partition into Plane Subgraphs (CG Challenge)

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

• Publication year

  2022

• Venue

  International Symposium on Computational Geometry

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.4230/LIPIcs.SoCG.2022.71
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Conflict-Based Local Search for Minimum Partition into Plane Subgraphs (CG Challenge)

  2022cited by this paper
• Minimum Partition into Plane Subgraphs: The CG:SHOP Challenge 2022

  2022cited by this paper
• Local Search with Weighting Schemes for the CG: SHOP 2022 Competition (CG Challenge)

  2022cited by this paper
• SAT-Based Local Search for Plane Subgraph Partitions

  2022cited by this paper
• Shadoks Approach to Low-Makespan Coordinated Motion Planning

  2021cited by this paper
• Guide to Graph Colouring: Algorithms and Applications

  2015cited by this paper
• Graph Coloring Algorithms

  2014cited by this paper
• Graph Coloring Problems

  2013cited by this paper
• Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation

  2012cited by this paper
• An exact method for graph coloring

  2006cited by this paper
• A Branch-and-Cut algorithm for graph coloring

  2006cited by this paper
• Hybrid Evolutionary Algorithms for Graph Coloring

  1999cited by this paper
• "Squeaky Wheel" Optimization

  1998cited by this paper
• Using tabu search techniques for graph coloring

  1987cited by this paper
• New methods to color the vertices of a graph

  1979cited by this paper
• Journal of Graph Algorithms and Applications Small Maximal Independent Sets and Faster Exact Graph Coloring

  year unknowncited by this paper

• Minimum Non-Obtuse Triangulations: The CG:SHOP Challenge 2025

  2025cites this paper
• Maximum Polygon Packing: The CG: SHOP Challenge 2024

  2024cites this paper
• Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph Coloring

  2023cites this paper
• SAT-boosted Tabu Search for Coloring Massive Graphs

  2023cites this paper
• Minimum Partition into Plane Subgraphs: The CG:SHOP Challenge 2022

  2022cites this paper
• SAT-Based Local Search for Plane Subgraph Partitions

  2022cites this paper
• Local Search with Weighting Schemes for the CG: SHOP 2022 Competition (CG Challenge)

  2022cites this paper
• Conflict-Based Local Search for Minimum Partition into Plane Subgraphs (CG Challenge)

  2022cites this paper