DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2026.42

Computing Twin-Width via Treedepth and Vertex Integrity

Authors: Robert Ganian and Mathis Rocton

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract

Twin-width is a graph parameter that has become central to explaining the fixed-parameter tractability of first-order model checking across many graph classes. Despite its algorithmic importance, computing twin-width remains poorly understood: even recognizing graphs of twin-width at most four is NP-hard, and no fixed-parameter approximations parameterized by twin-width itself are known. A recent approach towards breaking this barrier focuses on first developing fixed-parameter algorithms for computing or approximating twin-width under parameterizations distinct from twin-width. Our first result establishes that approximating twin-width is fixed-parameter tractable when parameterized by treedepth, thereby breaking the long-standing barrier that all previous tractable parameterizations were based on deletion distance. The proof proceeds via oriented twin-width, yielding the first constructive evidence that this variant may be easier to handle algorithmically. As our second main result, we show that computing twin-width exactly is fixed-parameter tractable with respect to vertex integrity. This constitutes the first non-trivial parameterized algorithm for computing optimal contraction sequences.

Cite as

Robert Ganian and Mathis Rocton. Computing Twin-Width via Treedepth and Vertex Integrity. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 42:1-42:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ganian_et_al:LIPIcs.STACS.2026.42,
  author =	{Ganian, Robert and Rocton, Mathis},
  title =	{{Computing Twin-Width via Treedepth and Vertex Integrity}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{42:1--42:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.42},
  URN =		{urn:nbn:de:0030-drops-255318},
  doi =		{10.4230/LIPIcs.STACS.2026.42},
  annote =	{Keywords: twin-width, fixed-parameter algorithms, treedepth, vertex integrity}
}

Document

PACE Solver Description

DOI: 10.4230/LIPIcs.IPEC.2025.35

PACE Solver Description: Bad Dominating Set Maker

Authors: Alexander Dobler, Simon Dominik Fink, and Mathis Rocton

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract

Dominating Set and Hitting Set are two well-known NP-hard problems on graphs and hypergraphs, respectively. For Dominating Set, we seek a subset S of vertices of minimum size, such that every vertex has a neighbor in S. For Hitting Set, we require that this minimum size subset S intersects each hyperedge. We present Bad Dominating Set Maker, our solver for both problems posed in the exact tracks of the 2025 PACE Challenge. It uses reduction rules, dynamic programming on tree decompositions, and external Vertex Cover and SAT solvers.

Cite as

Alexander Dobler, Simon Dominik Fink, and Mathis Rocton. PACE Solver Description: Bad Dominating Set Maker. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 35:1-35:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dobler_et_al:LIPIcs.IPEC.2025.35,
  author =	{Dobler, Alexander and Fink, Simon Dominik and Rocton, Mathis},
  title =	{{PACE Solver Description: Bad Dominating Set Maker}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{35:1--35:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.35},
  URN =		{urn:nbn:de:0030-drops-251673},
  doi =		{10.4230/LIPIcs.IPEC.2025.35},
  annote =	{Keywords: Dominating Set, Hitting Set, Pace Challenge}
}

Document

Invited Paper

DOI: 10.4230/OASIcs.RW.2024/2025.8

ASP Essentials: Modelling and Efficient Solving (Invited Paper)

Authors: Giuseppe Mazzotta and Francesco Ricca

Published in: OASIcs, Volume 138, Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 & RW 2025)

Abstract

Answer Set Programming (ASP) is a logic-based Knowledge Representation and Reasoning (KRR) paradigm that facilitates rapid prototyping of solutions for complex problems. It is particularly effective for tackling Deep Reasoning tasks involving exponentially large search spaces, such as combinatorial search and optimization. While getting started with ASP is relatively easy, mastering its advanced constructs and scaling solutions to real-world problem sizes can be challenging. This paper provides an introduction to ASP, guiding the reader from the fundamentals of the language to the application of programming methodologies and the computation of answer sets. Beyond the core framework, the paper also examines selected extensions of ASP that enable the modeling of complex problems, as well as compilation techniques designed to enhance solving efficiency. Furthermore, it mentions some recent tools that combine ASP with LLMs.

Cite as

Giuseppe Mazzotta and Francesco Ricca. ASP Essentials: Modelling and Efficient Solving (Invited Paper). In Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 & RW 2025). Open Access Series in Informatics (OASIcs), Volume 138, pp. 8:1-8:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mazzotta_et_al:OASIcs.RW.2024/2025.8,
  author =	{Mazzotta, Giuseppe and Ricca, Francesco},
  title =	{{ASP Essentials: Modelling and Efficient Solving}},
  booktitle =	{Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 \& RW 2025)},
  pages =	{8:1--8:21},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-405-5},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{138},
  editor =	{Artale, Alessandro and Bienvenu, Meghyn and Garc{\'\i}a, Yazm{\'\i}n Ib\'{a}\~{n}ez and Murlak, Filip},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.RW.2024/2025.8},
  URN =		{urn:nbn:de:0030-drops-250539},
  doi =		{10.4230/OASIcs.RW.2024/2025.8},
  annote =	{Keywords: Answer Set Programming, ASP with Quantifiers, Grounding Bottleneck, Compilation-based ASP solving, Neurosymbolic AI, LLMs}
}

Document

Invited Paper

DOI: 10.4230/OASIcs.RW.2024/2025.5

Inconsistency-Tolerant Semantics Based on (Preferred) Repairs (Invited Paper)

Authors: Camille Bourgaux

Published in: OASIcs, Volume 138, Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 & RW 2025)

Abstract

Real-world datasets are plagued by data quality issues which may render the data inconsistent w.r.t. a set of constraints, be they given by database integrity constraints or ontologies. A prominent way to handle such inconsistent data is to use inconsistency-tolerant semantics to obtain meaningful answers to queries. Most of these semantics are based on some notion of repairs, which represent ways of restoring the data consistency. The most basic kind of repairs is that of subset repairs, which are maximal consistent subsets of the dataset. However, in many scenarios, one can define preferred repairs based on some preference information. These lecture notes present inconsistency-tolerant semantics, focusing on the repair-based ones, then review different kinds of preferred repairs that have been considered in the literature. We present in particular the relationships between different kinds of preferred repairs and other notions related to inconsistency handling, the computational complexity of reasoning with (preferred) repairs, and some implementations.

Cite as

Camille Bourgaux. Inconsistency-Tolerant Semantics Based on (Preferred) Repairs (Invited Paper). In Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 & RW 2025). Open Access Series in Informatics (OASIcs), Volume 138, pp. 5:1-5:67, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bourgaux:OASIcs.RW.2024/2025.5,
  author =	{Bourgaux, Camille},
  title =	{{Inconsistency-Tolerant Semantics Based on (Preferred) Repairs}},
  booktitle =	{Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 \& RW 2025)},
  pages =	{5:1--5:67},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-405-5},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{138},
  editor =	{Artale, Alessandro and Bienvenu, Meghyn and Garc{\'\i}a, Yazm{\'\i}n Ib\'{a}\~{n}ez and Murlak, Filip},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.RW.2024/2025.5},
  URN =		{urn:nbn:de:0030-drops-250504},
  doi =		{10.4230/OASIcs.RW.2024/2025.5},
  annote =	{Keywords: Knowledge bases, databases, inconsistency handling, repairs, preferences}
}

Document

Invited Paper

DOI: 10.4230/OASIcs.RW.2024/2025.1

Rule-Based Knowledge Graph Completion (Invited Paper)

Authors: Patrick Betz, Christian Meilicke, and Heiner Stuckenschmidt

Published in: OASIcs, Volume 138, Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 & RW 2025)

Abstract

The field of knowledge graph completion is concerned with augmenting knowledge graphs with missing information. Symbolic rule-based approaches are not only efficient and interpretable but also competitive with embedding-based methods in regard to predictive quality. Rule-based knowledge graph completion can be separated into two stages, the learning stage and the application stage, which are both individually challenging. In the learning stage, horn rules are mined from a given knowledge graph. Given the vast size of the space of all possible rules, the mining approach must select relevant rules effectively. In the application stage, the mined rules are used to make new predictions which are assigned with plausibility scores. These scores need to be set by aggregating individual confidence values of rules that have the same consequence. This tutorial covers the fundamental aspects required to build a symbolic rule-based approach for knowledge graph completion. It will discuss the different rule types, mining strategies, and how to effectively apply the rules in different scenarios. Finally, we discuss practical examples for rule application by using the Python-based PyClause library.

Cite as

Patrick Betz, Christian Meilicke, and Heiner Stuckenschmidt. Rule-Based Knowledge Graph Completion (Invited Paper). In Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 & RW 2025). Open Access Series in Informatics (OASIcs), Volume 138, pp. 1:1-1:45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{betz_et_al:OASIcs.RW.2024/2025.1,
  author =	{Betz, Patrick and Meilicke, Christian and Stuckenschmidt, Heiner},
  title =	{{Rule-Based Knowledge Graph Completion}},
  booktitle =	{Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 \& RW 2025)},
  pages =	{1:1--1:45},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-405-5},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{138},
  editor =	{Artale, Alessandro and Bienvenu, Meghyn and Garc{\'\i}a, Yazm{\'\i}n Ib\'{a}\~{n}ez and Murlak, Filip},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.RW.2024/2025.1},
  URN =		{urn:nbn:de:0030-drops-250461},
  doi =		{10.4230/OASIcs.RW.2024/2025.1},
  annote =	{Keywords: Knowledge Graph Completion, Rule Learning, Symbolic AI}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2025.25

Structural Parameterizations of Simultaneous Planarity

Authors: Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, Matthias Pfretzschner, and Ignaz Rutter

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract

Given a set of graphs on the same vertex set, the problem Simultaneous Embedding With Fixed Edges (SEFE) asks, whether there exist planar drawings of all input graphs, such that every pair of drawings coincides on their shared subgraph. It is known that SEFE is NP-complete [Elisabeth Gassner et al., 2006], even in the so-called sunflower case, where all pairs of input graphs have the same shared graph G_∩ [Marcus Schaefer, 2012]. Fink, Pfretzschner, and Rutter [Simon D. Fink et al., 2023] recently initiated the study of the parameterized complexity of SEFE in the sunflower case, mainly focusing on structural parameters of G_∩. In this work, we shift the focus towards parameters of the union graph G_∪ that contains the edges of all input graphs. On the positive side, we establish fixed-parameter tractability for the problem with respect to the feedback edge set number of G_∪. We complement this result by showing that it, surprisingly, remains NP-complete even if G_∪ has constant vertex cover number. These results settle two open questions posed by Fink et al. [Simon D. Fink et al., 2023].

Cite as

Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, Matthias Pfretzschner, and Ignaz Rutter. Structural Parameterizations of Simultaneous Planarity. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{depian_et_al:LIPIcs.ISAAC.2025.25,
  author =	{Depian, Thomas and Fink, Simon D. and Firbas, Alexander and Ganian, Robert and Pfretzschner, Matthias and Rutter, Ignaz},
  title =	{{Structural Parameterizations of Simultaneous Planarity}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.25},
  URN =		{urn:nbn:de:0030-drops-249332},
  doi =		{10.4230/LIPIcs.ISAAC.2025.25},
  annote =	{Keywords: SEFE, Simultaneous Planarity, Fixed-Parameter Tractability, NP-hardness}
}

Document

DOI: 10.4230/LIPIcs.GD.2025.17

Visualizing Treewidth

Authors: Alvin Chiu, Thomas Depian, David Eppstein, Michael T. Goodrich, and Martin Nöllenburg

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract

A witness drawing of a graph is a visualization that clearly shows a given property of a graph. We study and implement various drawing paradigms for witness drawings to clearly show that graphs have bounded pathwidth or treewidth. Our approach draws the tree decomposition or path decomposition as a tree of bags, with induced subgraphs shown in each bag, and with "tracks" for each graph vertex connecting its copies in multiple bags. Within bags, we optimize the vertex layout to avoid crossings of edges and tracks. We implement a visualization prototype for crossing minimization using dynamic programming for graphs of small width and heuristic approaches for graphs of larger width. We introduce a taxonomy of drawing styles, which render the subgraph for each bag as an arc diagram with one or two pages or as a circular layout with straight-line edges, and we render tracks either with straight lines or with orbital-radial paths.

Cite as

Alvin Chiu, Thomas Depian, David Eppstein, Michael T. Goodrich, and Martin Nöllenburg. Visualizing Treewidth. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chiu_et_al:LIPIcs.GD.2025.17,
  author =	{Chiu, Alvin and Depian, Thomas and Eppstein, David and Goodrich, Michael T. and N\"{o}llenburg, Martin},
  title =	{{Visualizing Treewidth}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{17:1--17:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.17},
  URN =		{urn:nbn:de:0030-drops-250034},
  doi =		{10.4230/LIPIcs.GD.2025.17},
  annote =	{Keywords: Graph drawing, witness drawings, pathwidth, treewidth}
}

Document

DOI: 10.4230/LIPIcs.GD.2025.14

OOPS: Optimized One-Planarity Solver via SAT

Authors: Sergey Pupyrev

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract

We present OOPS (Optimized One-Planarity Solver), a practical heuristic for recognizing 1-planar graphs and several important subclasses. A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once - a natural generalization of planar graphs that has received increasing attention in graph drawing and beyond-planar graph theory. Although testing planarity can be done in linear time, recognizing 1-planar graphs is NP-complete, making effective practical algorithms especially valuable. The core idea of our approach is to reduce the recognition of 1-planarity to a propositional satisfiability (SAT) instance, enabling the use of modern SAT solvers to efficiently explore the search space. Despite the inherent complexity of the problem, our method is substantially faster in practice than naïve or brute-force algorithms. In addition to demonstrating the empirical performance of our solver on synthetic and real-world instances, we show how OOPS can be used as a discovery tool in theoretical graph theory. Specifically, we employ OOPS to investigate two research problems concerning 1-planarity of specific graph families. Our implementation of the algorithm is publicly available to support further exploration in the field.

Cite as

Sergey Pupyrev. OOPS: Optimized One-Planarity Solver via SAT. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pupyrev:LIPIcs.GD.2025.14,
  author =	{Pupyrev, Sergey},
  title =	{{OOPS: Optimized One-Planarity Solver via SAT}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{14:1--14:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.14},
  URN =		{urn:nbn:de:0030-drops-250004},
  doi =		{10.4230/LIPIcs.GD.2025.14},
  annote =	{Keywords: beyond planarity, 1-planar graph, SAT, book embeddings, upward 1-planarity}
}

Document

DOI: 10.4230/LIPIcs.GD.2025.39

Optimizing Wiggle in Storylines

Authors: Alexander Dobler, Tim Hegemann, Martin Nöllenburg, and Alexander Wolff

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract

A storyline visualization shows interactions between characters over time. Each character is represented by an x-monotone curve. Time is mapped to the x-axis, and groups of characters that interact at a particular point t in time must be ordered consecutively in the y-dimension at x = t. The predominant objective in storyline optimization so far has been the minimization of crossings between (blocks of) characters. Building on this work, we investigate another important, but less studied quality criterion, namely the minimization of wiggle, i.e., the amount of vertical movement of the characters over time. Given a storyline instance together with an ordering of the characters at any point in time, we show that wiggle count minimization is NP-complete. In contrast, we provide algorithms based on mathematical programming to solve linear wiggle height minimization and quadratic wiggle height minimization efficiently. Finally, we introduce a new method for routing character curves that focuses on keeping distances between neighboring curves constant as long as they run in parallel. We have implemented our algorithms, and we conduct a case study that explores the differences between the three optimization objectives. We use existing benchmark data, but we also present a new use case for storylines, namely the visualization of rolling stock schedules in railway operation.

Cite as

Alexander Dobler, Tim Hegemann, Martin Nöllenburg, and Alexander Wolff. Optimizing Wiggle in Storylines. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dobler_et_al:LIPIcs.GD.2025.39,
  author =	{Dobler, Alexander and Hegemann, Tim and N\"{o}llenburg, Martin and Wolff, Alexander},
  title =	{{Optimizing Wiggle in Storylines}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{39:1--39:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.39},
  URN =		{urn:nbn:de:0030-drops-250252},
  doi =		{10.4230/LIPIcs.GD.2025.39},
  annote =	{Keywords: Storyline visualization, wiggle minimization, NP-complete, linear programming, quadratic programming, experimental analysis}
}

Document

DOI: 10.4230/LIPIcs.GD.2025.4

Heuristics for Exact 1-Planarity Testing

Authors: Simon D. Fink, Miriam Münch, Matthias Pfretzschner, and Ignaz Rutter

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract

Since many real-world graphs are nonplanar, the study of graphs that allow few crossings per edge has been an active subfield of graph theory in recent years. One of the most natural generalizations of planar graphs are the so-called 1-planar graphs that admit a drawing with at most one crossing per edge. Unfortunately, testing whether a graph is 1-planar is known to be NP-complete even for very restricted graph classes. On the positive side, Binucci, Didimo and Montecchiani [Binucci et al., 2023] presented the first practical algorithm for testing 1-planarity based on an easy-to-implement backtracking strategy. We build on this idea and systematically explore the design choices of such algorithms and propose several new ingredients, such as different branching strategies and multiple filter criteria that allow us to reject certain branches in the search tree early on. We conduct an extensive experimental evaluation that evaluates the efficiency and effectiveness of these ingredients. Given a time limit of three hours per instance, our best configuration is able to solve more than 95% of the non-planar instances from the well-known North and Rome graphs with up to 50 vertices. Notably, the median running time for solved instances is well below 4 seconds.

Cite as

Simon D. Fink, Miriam Münch, Matthias Pfretzschner, and Ignaz Rutter. Heuristics for Exact 1-Planarity Testing. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fink_et_al:LIPIcs.GD.2025.4,
  author =	{Fink, Simon D. and M\"{u}nch, Miriam and Pfretzschner, Matthias and Rutter, Ignaz},
  title =	{{Heuristics for Exact 1-Planarity Testing}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.4},
  URN =		{urn:nbn:de:0030-drops-249909},
  doi =		{10.4230/LIPIcs.GD.2025.4},
  annote =	{Keywords: 1-Planarity, Experiments, Backtracking}
}

Document

DOI: 10.4230/OASIcs.DX.2025.8

Safe to Fly? Real-Time Flight Mission Feasibility Assessment for Drone Package Delivery Operations

Authors: Abenezer Taye, Austin Coursey, Marcos Quinones-Grueiro, Chao Hu, Gautam Biswas, and Peng Wei

Published in: OASIcs, Volume 136, 36th International Conference on Principles of Diagnosis and Resilient Systems (DX 2025)

Abstract

Ensuring flight safety for small unmanned aerial systems (sUAS) requires continuous in-flight monitoring and decision-making, as unexpected events can alter power consumption and deplete battery energy faster than anticipated. Such events may result in insufficient battery capacity to complete a mission, thereby compromising flight safety. In this paper, we present an online feasibility assessment and contingency management framework that continuously monitors the aircraft’s battery state and the energy required to complete the flight in real-time, which enables informed decision-making to enhance flight safety. The framework consists of two main components: power consumption prediction and battery voltage trajectory prediction. The power consumption prediction is conducted using a model that is based on momentum theory, while the voltage trajectory prediction is performed using a Neural Ordinary Differential Equation (Neural ODE)-based data-driven model. By integrating these two components, the framework evaluates the feasibility of a flight mission in real time and determines whether to proceed with the mission or initiate rerouting. We evaluate the framework’s performance in a drone delivery scenario in the Dallas–Fort Worth (DFW) area, where the aircraft encounters an unexpected energy depletion event mid-flight. The proposed framework is tasked with assessing the feasibility of completing the mission and, if necessary, rerouting the aircraft for an emergency landing. The results demonstrate that the framework accurately and efficiently detects energy insufficiencies in real-time and re-routes the aircraft to a [3] predefined emergency landing site.

Cite as

Abenezer Taye, Austin Coursey, Marcos Quinones-Grueiro, Chao Hu, Gautam Biswas, and Peng Wei. Safe to Fly? Real-Time Flight Mission Feasibility Assessment for Drone Package Delivery Operations. In 36th International Conference on Principles of Diagnosis and Resilient Systems (DX 2025). Open Access Series in Informatics (OASIcs), Volume 136, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{taye_et_al:OASIcs.DX.2025.8,
  author =	{Taye, Abenezer and Coursey, Austin and Quinones-Grueiro, Marcos and Hu, Chao and Biswas, Gautam and Wei, Peng},
  title =	{{Safe to Fly? Real-Time Flight Mission Feasibility Assessment for Drone Package Delivery Operations}},
  booktitle =	{36th International Conference on Principles of Diagnosis and Resilient Systems (DX 2025)},
  pages =	{8:1--8:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-394-2},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{136},
  editor =	{Quinones-Grueiro, Marcos and Biswas, Gautam and Pill, Ingo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.DX.2025.8},
  URN =		{urn:nbn:de:0030-drops-247970},
  doi =		{10.4230/OASIcs.DX.2025.8},
  annote =	{Keywords: Battery Modeling, Neural ODE, Unmanned Aerial Vehicles}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2025.2

A Geometric Approach to Integrated Periodic Timetabling and Passenger Routing

Authors: Fabian Löbel and Niels Lindner

Published in: OASIcs, Volume 137, 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)

Abstract

We offer a geometric perspective on the problem of integrated periodic timetabling and passenger routing in public transport. Inside the space of periodic tensions, we single out those regions, where the same set of paths provides shortest passenger routes. This results in a polyhedral subdivision, which we combine with the known decomposition by polytropes. On each maximal region of the common refinement, the integrated problem is solvable in polynomial time. We transform these insights into a new geometry-driven primal heuristic, integrated tropical neighborhood search (ITNS). Computationally, we compare implementations of ITNS and the integrated (restricted) modulo network simplex algorithm on the TimPassLib benchmark set, and contribute better solutions in terms of total travel time for all but one of the twenty-five instances for which a proven optimal solution is not yet known.

Cite as

Fabian Löbel and Niels Lindner. A Geometric Approach to Integrated Periodic Timetabling and Passenger Routing. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 2:1-2:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lobel_et_al:OASIcs.ATMOS.2025.2,
  author =	{L\"{o}bel, Fabian and Lindner, Niels},
  title =	{{A Geometric Approach to Integrated Periodic Timetabling and Passenger Routing}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{2:1--2:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-404-8},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{137},
  editor =	{Sauer, Jonas and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.2},
  URN =		{urn:nbn:de:0030-drops-247580},
  doi =		{10.4230/OASIcs.ATMOS.2025.2},
  annote =	{Keywords: Periodic Timetabling, Passenger Routing, Polyhedral Complexes}
}

Document

DOI: 10.4230/LIPIcs.ESA.2025.15

Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms

Authors: Thomas Depian, Simon D. Fink, Robert Ganian, and Vaishali Surianarayanan

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract

In spite of the extensive study of stack and queue layouts, many fundamental questions remain open concerning the complexity-theoretic frontiers for computing stack and queue layouts. A stack (resp. queue) layout places vertices along a line and assigns edges to pages so that no two edges on the same page are crossing (resp. nested). We provide three new algorithms which together substantially expand our understanding of these problems: 1) A fixed-parameter algorithm for computing minimum-page stack and queue layouts w.r.t. the vertex integrity of an n-vertex graph G. This result is motivated by an open question in the literature and generalizes the previous algorithms parameterizing by the vertex cover number of G. The proof relies on a newly developed Ramsey pruning technique. Vertex integrity intuitively measures the vertex deletion distance to a subgraph with only small connected components. 2) An n^𝒪(q 𝓁) algorithm for computing 𝓁-page stack and queue layouts of page width at most q. This is the first algorithm avoiding a double-exponential dependency on the parameters. The page width of a layout measures the maximum number of edges one needs to cross on any page to reach the outer face. 3) A 2^𝒪(n) algorithm for computing 1-page queue layouts. This improves upon the previously fastest n^𝒪(n) algorithm and can be seen as a counterpart to the recent subexponential algorithm for computing 2-page stack layouts [ICALP'24], but relies on an entirely different technique.

Cite as

Thomas Depian, Simon D. Fink, Robert Ganian, and Vaishali Surianarayanan. Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{depian_et_al:LIPIcs.ESA.2025.15,
  author =	{Depian, Thomas and Fink, Simon D. and Ganian, Robert and Surianarayanan, Vaishali},
  title =	{{Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.15},
  URN =		{urn:nbn:de:0030-drops-244835},
  doi =		{10.4230/LIPIcs.ESA.2025.15},
  annote =	{Keywords: stack layouts, queue layouts, parameterized algorithms, vertex integrity, Ramsey theory}
}

Document

DOI: 10.4230/LIPIcs.ECOOP.2025.16

A Lightweight Method for Generating Multi-Tier JIT Compilation Virtual Machine in a Meta-Tracing Compiler Framework

Authors: Yusuke Izawa, Hidehiko Masuhara, and Carl Friedrich Bolz-Tereick

Published in: LIPIcs, Volume 333, 39th European Conference on Object-Oriented Programming (ECOOP 2025)

Abstract

Meta-compiler frameworks, such as RPython and Graal/Truffle, generate high-performance virtual machines (VMs) from interpreter definitions. Although they generate VMs with high-quality just-in-time (JIT) compilers, they still lack an important feature that dedicated VMs (i.e., VMs that are developed for specific languages) have, namely multi-tier compilation. Multi-tier compilation uses light-weight compilers at early stages and highly optimizing compilers at later stages in order to balance between compilation overheads and code quality. We propose a novel approach to enabling multi-tier compilation in the VMs generated by a meta-compiler framework. Instead of extending the JIT compiler backend of the framework, our approach drives an existing (heavyweight) compiler backend in the framework to quickly generate unoptimized native code by merely embedding directives and compile-time operations into interpreter definitions. As a validation of the approach, we developed 2SOM, a Simple Object Machine with a two-tier JIT compiler based on RPython. 2SOM first applies the tier-1 threaded code generator that is generated by our proposed technique, then, to the loops that exceed a threshold, applies the tier-2 tracing JIT compiler that is generated by the original RPython framework. Our performance evaluation that runs a program with a realistic workload showed that 2SOM improved, when compared against an RPython-based VM, warm-up performance by 15%, with merely a 5% reduction in peak performance.

Cite as

Yusuke Izawa, Hidehiko Masuhara, and Carl Friedrich Bolz-Tereick. A Lightweight Method for Generating Multi-Tier JIT Compilation Virtual Machine in a Meta-Tracing Compiler Framework. In 39th European Conference on Object-Oriented Programming (ECOOP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 333, pp. 16:1-16:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{izawa_et_al:LIPIcs.ECOOP.2025.16,
  author =	{Izawa, Yusuke and Masuhara, Hidehiko and Bolz-Tereick, Carl Friedrich},
  title =	{{A Lightweight Method for Generating Multi-Tier JIT Compilation Virtual Machine in a Meta-Tracing Compiler Framework}},
  booktitle =	{39th European Conference on Object-Oriented Programming (ECOOP 2025)},
  pages =	{16:1--16:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-373-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{333},
  editor =	{Aldrich, Jonathan and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2025.16},
  URN =		{urn:nbn:de:0030-drops-233090},
  doi =		{10.4230/LIPIcs.ECOOP.2025.16},
  annote =	{Keywords: virtual machine, JIT compiler, multi-tier JIT compiler, meta-tracing JIT compiler, RPython}
}

Document

DOI: 10.4230/LIPIcs.ECOOP.2025.19

Profile-Guided Field Externalization in an Ahead-Of-Time Compiler

Authors: Sebastian Kloibhofer, Lukas Makor, Peter Hofer, David Leopoldseder, and Hanspeter Mössenböck

Published in: LIPIcs, Volume 333, 39th European Conference on Object-Oriented Programming (ECOOP 2025)

Abstract

Field externalization is a technique to reduce the footprint of objects by removing fields that most frequently contain zero or null. While researchers have developed ways to bring this optimization into the Java world, these have been limited to research compilers or virtual machines for embedded systems. In this work, we present a novel field externalization technique that uses information from static analysis and profiling to determine externalizable fields. During compilation, we remove those fields and define companion classes. These are used in case of non-default-value writes to the externalized fields. Our approach also correctly handles synchronization to prevent issues in multithreaded environments. We integrated our approach into the modern Java ahead-of-time compiler GraalVM Native Image. We conducted an evaluation on a diverse set of benchmarks that includes standard and microservice-based benchmarks. For standard benchmarks, our approach reduces the total allocated bytes by 2.76% and the maximum resident set size (max-RSS) by 2.55%. For microservice benchmarks, we achieved a reduction of 6.88% for normalized allocated bytes and 2.45% for max-RSS. We computed these improvements via the geometric mean. The median reductions are are 1.46% (alloc. bytes) and 0.22% (max-RSS) in standard benchmarks, as well as 3.63% (alloc. bytes) and 0.20% (max-RSS) in microservice benchmarks.

Cite as

Sebastian Kloibhofer, Lukas Makor, Peter Hofer, David Leopoldseder, and Hanspeter Mössenböck. Profile-Guided Field Externalization in an Ahead-Of-Time Compiler. In 39th European Conference on Object-Oriented Programming (ECOOP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 333, pp. 19:1-19:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kloibhofer_et_al:LIPIcs.ECOOP.2025.19,
  author =	{Kloibhofer, Sebastian and Makor, Lukas and Hofer, Peter and Leopoldseder, David and M\"{o}ssenb\"{o}ck, Hanspeter},
  title =	{{Profile-Guided Field Externalization in an Ahead-Of-Time Compiler}},
  booktitle =	{39th European Conference on Object-Oriented Programming (ECOOP 2025)},
  pages =	{19:1--19:32},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-373-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{333},
  editor =	{Aldrich, Jonathan and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2025.19},
  URN =		{urn:nbn:de:0030-drops-233121},
  doi =		{10.4230/LIPIcs.ECOOP.2025.19},
  annote =	{Keywords: compilation, instrumentation, profiling, fields, externalization, memory footprint reduction, memory footprint optimization}
}

@InProceedings{kloibhofer_et_al:LIPIcs.ECOOP.2025.19,
  author =	{Kloibhofer, Sebastian and Makor, Lukas and Hofer, Peter and Leopoldseder, David and M\"{o}ssenb\"{o}ck, Hanspeter},
  title =	{{Profile-Guided Field Externalization in an Ahead-Of-Time Compiler}},
  booktitle =	{39th European Conference on Object-Oriented Programming (ECOOP 2025)},
  pages =	{19:1--19:32},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-373-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{333},
  editor =	{Aldrich, Jonathan and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2025.19},
  URN =		{urn:nbn:de:0030-drops-233121},
  doi =		{10.4230/LIPIcs.ECOOP.2025.19},
  annote =	{Keywords: compilation, instrumentation, profiling, fields, externalization, memory footprint reduction, memory footprint optimization}
}

24 Search Results for "Fink, Michael"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message