2026-07-22T00:13:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11151 2024-03-06T10:47:34Z ddc:004 open_access

Stronger ILPs for the Graph Genus Problem Chimani, Markus Wiedera, Tilo algorithm engineering genus integer linear programming The minimum genus of a graph is an important question in graph theory and a key ingredient in several graph algorithms. However, its computation is NP-hard and turns out to be hard even in practice. Only recently, the first non-trivial approach - based on SAT and ILP (integer linear programming) models - has been presented, but it is unable to successfully tackle graphs of genus larger than 1 in practice. Herein, we show how to improve the ILP formulation. The crucial ingredients are two-fold. First, we show that instead of modeling rotation schemes explicitly, it suffices to optimize over partitions of the (bidirected) arc set A of the graph. Second, we exploit the cycle structure of the graph, explicitly mapping short closed walks on A to faces in the embedding. Besides the theoretical advantages of our models, we show their practical strength by a thorough experimental evaluation. Contrary to the previous approach, we are able to quickly solve many instances of genus > 1. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Markus Chimani and Tilo Wiedera 2019 Is Part Of LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2019.30 urn:nbn:de:0030-drops-111511 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.30 eng https://creativecommons.org/licenses/by/3.0/legalcode