Search Results

Documents authored by Wallinger, Markus

Document
DOI: 10.4230/LIPIcs.ISAAC.2024.26
Constrained Boundary Labeling

Authors: Thomas Depian, Martin Nöllenburg, Soeren Terziadis, and Markus Wallinger

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
Boundary labeling is a technique in computational geometry used to label dense sets of feature points in an illustration. It involves placing labels along an axis-aligned bounding box and connecting each label with its corresponding feature point using non-crossing leader lines. Although boundary labeling is well-studied, semantic constraints on the labels have not been investigated thoroughly. In this paper, we introduce grouping and ordering constraints in boundary labeling: Grouping constraints enforce that all labels in a group are placed consecutively on the boundary, and ordering constraints enforce a partial order over the labels. We show that it is NP-hard to find a labeling for arbitrarily sized labels with unrestricted positions along one side of the boundary. However, we obtain polynomial-time algorithms if we restrict this problem either to uniform-height labels or to a finite set of candidate positions. Finally, we show that finding a labeling on two opposite sides of the boundary is NP-complete, even for uniform-height labels and finite label positions.
Cite as

Thomas Depian, Martin Nöllenburg, Soeren Terziadis, and Markus Wallinger. Constrained Boundary Labeling. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{depian_et_al:LIPIcs.ISAAC.2024.26,
  author =	{Depian, Thomas and N\"{o}llenburg, Martin and Terziadis, Soeren and Wallinger, Markus},
  title =	{{Constrained Boundary Labeling}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{26:1--26:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.26},
  URN =		{urn:nbn:de:0030-drops-221539},
  doi =		{10.4230/LIPIcs.ISAAC.2024.26},
  annote =	{Keywords: Boundary labeling, Grouping constraints, Ordering constraints}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.15
Bundling-Aware Graph Drawing

Authors: Daniel Archambault, Giuseppe Liotta, Martin Nöllenburg, Tommaso Piselli, Alessandra Tappini, and Markus Wallinger

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
Edge bundling algorithms significantly improve the visualization of dense graphs by reducing the clutter of many edges visible on screen by bundling them together. As such, bundling is often viewed as a post-processing step applied to a drawing, and the vast majority of edge bundling algorithms consider a graph and its drawing as input. Another way of thinking about edge bundling is to simultaneously optimize both the drawing and the bundling. In this paper, we investigate methods to simultaneously optimize a graph drawing and its bundling. We describe an algorithmic framework which consists of three main steps, namely Filter, Draw, and Bundle. We then propose two alternative implementations and experimentally compare them against the state-of-the-art approach and the simple idea of drawing and subsequently bundling the graph. The experiments confirm that bundled drawings created by our framework outperform previous approaches according to standard quality metrics for edge bundling.
Cite as

Daniel Archambault, Giuseppe Liotta, Martin Nöllenburg, Tommaso Piselli, Alessandra Tappini, and Markus Wallinger. Bundling-Aware Graph Drawing. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 15:1-15:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{archambault_et_al:LIPIcs.GD.2024.15,
  author =	{Archambault, Daniel and Liotta, Giuseppe and N\"{o}llenburg, Martin and Piselli, Tommaso and Tappini, Alessandra and Wallinger, Markus},
  title =	{{Bundling-Aware Graph Drawing}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{15:1--15:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.15},
  URN =		{urn:nbn:de:0030-drops-212995},
  doi =		{10.4230/LIPIcs.GD.2024.15},
  annote =	{Keywords: Edge Bundling, Experimental Comparison, Graph Sparsification}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.22
Boundary Labeling in a Circular Orbit

Authors: Annika Bonerath, Martin Nöllenburg, Soeren Terziadis, Markus Wallinger, and Jules Wulms

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
Boundary labeling is a well-known method for displaying short textual labels for a set of point features in a figure alongside the boundary of that figure. Labels and their corresponding points are connected via crossing-free leaders. We propose orbital boundary labeling as a new variant of the problem, in which (i) the figure is enclosed by a circular contour and (ii) the labels are placed as disjoint circular arcs in an annulus-shaped orbit around the contour. The algorithmic objective is to compute an orbital boundary labeling with the minimum total leader length. We identify several parameters that define the corresponding problem space: two leader types (straight or orbital-radial), label size and order, presence of candidate label positions, and constraints on where a leader attaches to its label. Our results provide polynomial-time algorithms for many variants and NP-hardness for others, using a variety of geometric and combinatorial insights.
Cite as

Annika Bonerath, Martin Nöllenburg, Soeren Terziadis, Markus Wallinger, and Jules Wulms. Boundary Labeling in a Circular Orbit. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bonerath_et_al:LIPIcs.GD.2024.22,
  author =	{Bonerath, Annika and N\"{o}llenburg, Martin and Terziadis, Soeren and Wallinger, Markus and Wulms, Jules},
  title =	{{Boundary Labeling in a Circular Orbit}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.22},
  URN =		{urn:nbn:de:0030-drops-213060},
  doi =		{10.4230/LIPIcs.GD.2024.22},
  annote =	{Keywords: External labeling, Orthoradial drawing, NP-hardness, Polynomial algorithms}
}
Document
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2024.45
GdMetriX - A NetworkX Extension For Graph Drawing Metrics (Poster Abstract)

Authors: Martin Nöllenburg, Sebastian Röder, and Markus Wallinger

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
networkX is a well-established Python library for network analysis. With gdMetriX, we aim to extend the functionality of networkX and provide common quality metrics used in the field of graph drawing, such as the number of crossings or the angular resolution. In addition, the package provides easy-to-use access to the graph datasets provided by the ’Graph Layout Benchmark Datasets’ project from the Northeastern University Visualization Lab.
Cite as

Martin Nöllenburg, Sebastian Röder, and Markus Wallinger. GdMetriX - A NetworkX Extension For Graph Drawing Metrics (Poster Abstract). In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 45:1-45:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{nollenburg_et_al:LIPIcs.GD.2024.45,
  author =	{N\"{o}llenburg, Martin and R\"{o}der, Sebastian and Wallinger, Markus},
  title =	{{GdMetriX - A NetworkX Extension For Graph Drawing Metrics}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{45:1--45:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.45},
  URN =		{urn:nbn:de:0030-drops-213294},
  doi =		{10.4230/LIPIcs.GD.2024.45},
  annote =	{Keywords: Graph Drawing Metrics}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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