7 Search Results for "Barth, Lukas"

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.WADS.2025.40
Grandchildren-Weight-Balanced Binary Search Trees

Authors: Vincent Jugé

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
We revisit weight-balanced trees, also known as trees of bounded balance. Invented by Nievergelt and Reingold in 1972, these trees are obtained by assigning a weight to each node and requesting that the weight of each node should be quite larger than the weights of its children, the precise meaning of "quite larger" depending on a real-valued parameter γ. Blum and Mehlhorn then showed how to maintain them in a recursive (bottom-up) fashion when 2/11 ⩽ γ ⩽ 1-1/√2, their algorithm requiring only an amortised constant number of tree rebalancing operations per update (insertion or deletion). Later, in 1993, Lai and Wood proposed a top-down procedure for updating these trees when 2/11 ⩽ γ ⩽ 1/4. Our contribution is two-fold. First, we strengthen the requirements of Nievergelt and Reingold, by also requesting that each node should have a substantially larger weight than its grandchildren, thereby obtaining what we call grandchildren-balanced trees. Grandchildren-balanced trees are not harder to maintain than weight-balanced trees, but enjoy a smaller node depth, both in the worst case (with a 6 % decrease) and on average (with a 1.6 % decrease). In particular, unlike standard weight-balanced trees, all grandchildren-balanced trees with n nodes are of height less than 2 log₂(n). Second, we adapt the algorithm of Lai and Wood to all weight-balanced trees, i.e., to all parameter values γ such that 2/11 ⩽ γ ⩽ 1-1/√2. More precisely, we adapt it to all grandchildren-balanced trees for which 1/4 < γ ⩽ 1 - 1/√2. Finally, we show that, except in limit cases (where, for instance, γ = 1 - 1/√2), all these algorithms result in making a constant amortised number of tree rebalancing operations per tree update.
Cite as

Vincent Jugé. Grandchildren-Weight-Balanced Binary Search Trees. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 40:1-40:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{juge:LIPIcs.WADS.2025.40,
  author =	{Jug\'{e}, Vincent},
  title =	{{Grandchildren-Weight-Balanced Binary Search Trees}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{40:1--40:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.40},
  URN =		{urn:nbn:de:0030-drops-242710},
  doi =		{10.4230/LIPIcs.WADS.2025.40},
  annote =	{Keywords: Data structures, Balanced binary trees}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.41
Residue Domination in Bounded-Treewidth Graphs

Authors: Jakob Greilhuber, Philipp Schepper, and Philip Wellnitz

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
For the vertex selection problem (σ,ρ)-DomSet one is given two fixed sets σ and ρ of integers and the task is to decide whether we can select vertices of the input graph such that, for every selected vertex, the number of selected neighbors is in σ and, for every unselected vertex, the number of selected neighbors is in ρ [Telle, Nord. J. Comp. 1994]. This framework covers many fundamental graph problems such as Independent Set and Dominating Set. We significantly extend the recent result by Focke et al. [SODA 2023] to investigate the case when σ and ρ are two (potentially different) residue classes modulo m ≥ 2. We study the problem parameterized by treewidth and present an algorithm that solves in time m^tw ⋅ n^O(1) the decision, minimization and maximization version of the problem. This significantly improves upon the known algorithms where for the case m ≥ 3 not even an explicit running time is known. We complement our algorithm by providing matching lower bounds which state that there is no (m-ε)^pw ⋅ n^O(1)-time algorithm parameterized by pathwidth pw, unless SETH fails. For m = 2, we extend these bounds to the minimization version as the decision version is efficiently solvable.
Cite as

Jakob Greilhuber, Philipp Schepper, and Philip Wellnitz. Residue Domination in Bounded-Treewidth Graphs. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 41:1-41:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{greilhuber_et_al:LIPIcs.STACS.2025.41,
  author =	{Greilhuber, Jakob and Schepper, Philipp and Wellnitz, Philip},
  title =	{{Residue Domination in Bounded-Treewidth Graphs}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{41:1--41:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine 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.2025.41},
  URN =		{urn:nbn:de:0030-drops-228675},
  doi =		{10.4230/LIPIcs.STACS.2025.41},
  annote =	{Keywords: Parameterized Complexity, Treewidth, Generalized Dominating Set, Strong Exponential Time Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.SEA.2020.25
Zipping Segment Trees

Authors: Lukas Barth and Dorothea Wagner

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract
Stabbing queries in sets of intervals are usually answered using segment trees. A dynamic variant of segment trees has been presented by van Kreveld and Overmars, which uses red-black trees to do rebalancing operations. This paper presents zipping segment trees - dynamic segment trees based on zip trees, which were recently introduced by Tarjan et al. To facilitate zipping segment trees, we show how to uphold certain segment tree properties during the operations of a zip tree. We present an in-depth experimental evaluation and comparison of dynamic segment trees based on red-black trees, weight-balanced trees and several variants of the novel zipping segment trees. Our results indicate that zipping segment trees perform better than rotation-based alternatives.
Cite as

Lukas Barth and Dorothea Wagner. Zipping Segment Trees. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 25:1-25:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{barth_et_al:LIPIcs.SEA.2020.25,
  author =	{Barth, Lukas and Wagner, Dorothea},
  title =	{{Zipping Segment Trees}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{25:1--25:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.25},
  URN =		{urn:nbn:de:0030-drops-120990},
  doi =		{10.4230/LIPIcs.SEA.2020.25},
  annote =	{Keywords: Segment Trees, Dynamic Segment Trees, Zip Trees, Data Structures}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.52
Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm

Authors: Lars Gottesbüren, Michael Hamann, and Dorothea Wagner

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
In this paper, we propose HyperFlowCutter, an algorithm for balanced hypergraph bipartitioning that is based on minimum S-T hyperedge cuts and maximum flows. It computes a sequence of bipartitions that optimize cut size and balance in the Pareto sense, being able to trade one for the other. HyperFlowCutter builds on the FlowCutter algorithm for partitioning graphs. We propose additional features, such as handling disconnected hypergraphs, novel methods for obtaining starting S,T pairs as well as an approach to refine a given partition with HyperFlowCutter. Our main contribution is ReBaHFC, a new algorithm which obtains an initial partition with the fast multilevel hypergraph partitioner PaToH and then improves it using HyperFlowCutter as a refinement algorithm. ReBaHFC is able to significantly improve the solution quality of PaToH at little additional running time. The solution quality is only marginally worse than that of the best-performing hypergraph partitioners KaHyPar and hMETIS, while being one order of magnitude faster. Thus ReBaHFC offers a new time-quality trade-off in the current spectrum of hypergraph partitioners. For the special case of perfectly balanced bipartitioning, only the much slower plain HyperFlowCutter yields slightly better solutions than ReBaHFC, while only PaToH is faster than ReBaHFC.
Cite as

Lars Gottesbüren, Michael Hamann, and Dorothea Wagner. Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 52:1-52:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gottesburen_et_al:LIPIcs.ESA.2019.52,
  author =	{Gottesb\"{u}ren, Lars and Hamann, Michael and Wagner, Dorothea},
  title =	{{Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{52:1--52:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.52},
  URN =		{urn:nbn:de:0030-drops-111730},
  doi =		{10.4230/LIPIcs.ESA.2019.52},
  annote =	{Keywords: Hypergraph Partitioning, Maximum Flows, Algorithm Engineering}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.55
Engineering Negative Cycle Canceling for Wind Farm Cabling

Authors: Sascha Gritzbach, Torsten Ueckerdt, Dorothea Wagner, Franziska Wegner, and Matthias Wolf

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
In a wind farm turbines convert wind energy into electrical energy. The generation of each turbine is transmitted, possibly via other turbines, to a substation that is connected to the power grid. On every possible interconnection there can be at most one of various different cable types. Each cable type comes with a cost per unit length and with a capacity. Designing a cost-minimal cable layout for a wind farm to feed all turbine production into the power grid is called the Wind Farm Cabling Problem (WCP). We consider a formulation of WCP as a flow problem on a graph where the cost of a flow on an edge is modeled by a step function originating from the cable types. Recently, we presented a proof-of-concept for a negative cycle canceling-based algorithm for WCP [Sascha Gritzbach et al., 2018]. We extend key steps of that heuristic and build a theoretical foundation that explains how this heuristic tackles the problems arising from the special structure of WCP. A thorough experimental evaluation identifies the best setup of the algorithm and compares it to existing methods from the literature such as Mixed-integer Linear Programming (MILP) and Simulated Annealing (SA). The heuristic runs in a range of half a millisecond to under two minutes on instances with up to 500 turbines. It provides solutions of similar quality compared to both competitors with running times of one hour and one day. When comparing the solution quality after a running time of two seconds, our algorithm outperforms the MILP- and SA-approaches, which allows it to be applied in interactive wind farm planning.
Cite as

Sascha Gritzbach, Torsten Ueckerdt, Dorothea Wagner, Franziska Wegner, and Matthias Wolf. Engineering Negative Cycle Canceling for Wind Farm Cabling. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 55:1-55:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gritzbach_et_al:LIPIcs.ESA.2019.55,
  author =	{Gritzbach, Sascha and Ueckerdt, Torsten and Wagner, Dorothea and Wegner, Franziska and Wolf, Matthias},
  title =	{{Engineering Negative Cycle Canceling for Wind Farm Cabling}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{55:1--55:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.55},
  URN =		{urn:nbn:de:0030-drops-111766},
  doi =		{10.4230/LIPIcs.ESA.2019.55},
  annote =	{Keywords: Negative Cycle Canceling, Step Cost Function, Wind Farm Planning}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.14
Towards a Topology-Shape-Metrics Framework for Ortho-Radial Drawings

Authors: Lukas Barth, Benjamin Niedermann, Ignaz Rutter, and Matthias Wolf

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Ortho-Radial drawings are a generalization of orthogonal drawings to grids that are formed by concentric circles and straight-line spokes emanating from the circles' center. Such drawings have applications in schematic graph layouts, e.g., for metro maps and destination maps. A plane graph is a planar graph with a fixed planar embedding. We give a combinatorial characterization of the plane graphs that admit a planar ortho-radial drawing without bends. Previously, such a characterization was only known for paths, cycles, and theta graphs, and in the special case of rectangular drawings for cubic graphs, where the contour of each face is required to be a rectangle. The characterization is expressed in terms of an ortho-radial representation that, similar to Tamassia's orthogonal representations for orthogonal drawings describes such a drawing combinatorially in terms of angles around vertices and bends on the edges. In this sense our characterization can be seen as a first step towards generalizing the Topology-Shape-Metrics framework of Tamassia to ortho-radial drawings.
Cite as

Lukas Barth, Benjamin Niedermann, Ignaz Rutter, and Matthias Wolf. Towards a Topology-Shape-Metrics Framework for Ortho-Radial Drawings. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{barth_et_al:LIPIcs.SoCG.2017.14,
  author =	{Barth, Lukas and Niedermann, Benjamin and Rutter, Ignaz and Wolf, Matthias},
  title =	{{Towards a Topology-Shape-Metrics Framework for Ortho-Radial Drawings}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.14},
  URN =		{urn:nbn:de:0030-drops-72234},
  doi =		{10.4230/LIPIcs.SoCG.2017.14},
  annote =	{Keywords: Graph Drawing, Ortho-Radial Drawings, Combinatorial Characterization, Bend Minimization, Topology-Shape-Metrics}
}
  • Refine by Type
  • 7 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 1 2020
  • 2 2019
  • 1 2017

  • Refine by Author
  • 3 Wagner, Dorothea
  • 2 Barth, Lukas
  • 2 Wolf, Matthias
  • 1 Chiu, Alvin
  • 1 Depian, Thomas
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs

  • Refine by Classification
  • 2 Mathematics of computing → Graph algorithms
  • 2 Theory of computation → Sorting and searching
  • 1 Human-centered computing → Graph drawings
  • 1 Information systems → Point lookups
  • 1 Mathematics of computing → Network flows
  • Show More...

  • Refine by Keyword
  • 1 Algorithm Engineering
  • 1 Balanced binary trees
  • 1 Bend Minimization
  • 1 Combinatorial Characterization
  • 1 Data Structures
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact