Search Results

Documents authored by Förster, Henry

Document
DOI: 10.4230/LIPIcs.GD.2024.11
Monotone Arc Diagrams with Few Biarcs

Authors: Steven Chaplick, Henry Förster, Michael Hoffmann, and Michael Kaufmann

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

Abstract
We show that every planar graph has a monotone topological 2-page book embedding where at most (4n-10)/5 (of potentially 3n-6) edges cross the spine, and every edge crosses the spine at most once; such an edge is called a biarc. We can also guarantee that all edges that cross the spine cross it in the same direction (e.g., from bottom to top). For planar 3-trees we can further improve the bound to (3n-9)/4, and for so-called Kleetopes we obtain a bound of at most (n-8)/3 edges that cross the spine. The bound for Kleetopes is tight, even if the drawing is not required to be monotone. A Kleetope is a plane triangulation that is derived from another plane triangulation T by inserting a new vertex v_f into each face f of T and then connecting v_f to the three vertices of f.
Cite as

Steven Chaplick, Henry Förster, Michael Hoffmann, and Michael Kaufmann. Monotone Arc Diagrams with Few Biarcs. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chaplick_et_al:LIPIcs.GD.2024.11,
  author =	{Chaplick, Steven and F\"{o}rster, Henry and Hoffmann, Michael and Kaufmann, Michael},
  title =	{{Monotone Arc Diagrams with Few Biarcs}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{11:1--11:16},
  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.11},
  URN =		{urn:nbn:de:0030-drops-212955},
  doi =		{10.4230/LIPIcs.GD.2024.11},
  annote =	{Keywords: planar graph, topological book embedding, monotone drawing, linear layout}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.16
GraphTrials: Visual Proofs of Graph Properties

Authors: Henry Förster, Felix Klesen, Tim Dwyer, Peter Eades, Seok-Hee Hong, Stephen G. Kobourov, Giuseppe Liotta, Kazuo Misue, Fabrizio Montecchiani, Alexander Pastukhov, and Falk Schreiber

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

Abstract
Graph and network visualization supports exploration, analysis and communication of relational data arising in many domains: from biological and social networks, to transportation and powergrid systems. With the arrival of AI-based question-answering tools, issues of trustworthiness and explainability of generated answers motivate a greater role for visualization. In the context of graphs, we see the need for visualizations that can convince a critical audience that an assertion about the graph under analysis is valid. The requirements for such representations that convey precisely one specific graph property are quite different from standard network visualization criteria which optimize general aesthetics and readability. In this paper, we aim to provide a comprehensive introduction to visual proofs of graph properties and a foundation for further research in the area. We present a framework that defines what it means to visually prove a graph property. In the process, we introduce the notion of a visual certificate, that is, a specialized faithful graph visualization that leverages the viewer’s perception, in particular, pre-attentive processing (e. g. via pop-out effects), to verify a given assertion about the represented graph. We also discuss the relationships between visual complexity, cognitive load and complexity theory, and propose a classification based on visual proof complexity. Finally, we provide examples of visual certificates for problems in different visual proof complexity classes.
Cite as

Henry Förster, Felix Klesen, Tim Dwyer, Peter Eades, Seok-Hee Hong, Stephen G. Kobourov, Giuseppe Liotta, Kazuo Misue, Fabrizio Montecchiani, Alexander Pastukhov, and Falk Schreiber. GraphTrials: Visual Proofs of Graph Properties. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{forster_et_al:LIPIcs.GD.2024.16,
  author =	{F\"{o}rster, Henry and Klesen, Felix and Dwyer, Tim and Eades, Peter and Hong, Seok-Hee and Kobourov, Stephen G. and Liotta, Giuseppe and Misue, Kazuo and Montecchiani, Fabrizio and Pastukhov, Alexander and Schreiber, Falk},
  title =	{{GraphTrials: Visual Proofs of Graph Properties}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{16:1--16:18},
  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.16},
  URN =		{urn:nbn:de:0030-drops-213005},
  doi =		{10.4230/LIPIcs.GD.2024.16},
  annote =	{Keywords: Graph Visualization, Theory of Visualization, Visual Proof}
}
Document
DOI: 10.4230/DagRep.14.2.71
Beyond-Planar Graphs: Models, Structures and Geometric Representations (Dagstuhl Seminar 24062)

Authors: Vida Dujmović, Seok-Hee Hong, Michael Kaufmann, János Pach, and Henry Förster

Published in: Dagstuhl Reports, Volume 14, Issue 2 (2024)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 24062 "Beyond-Planar Graphs: Models, Structures and Geometric Representations". The seminar investigated beyond-planar graphs, in particular, their combinatorial and topological structures, computational complexity and algorithmics for recognition, geometric representations, and their applications to real-world network visualization. Compared to the previous two editions of the seminar, we focus more on aspects of combinatorics and geometry. The program consists of four invited talks on beyond planar graphs, open problem session, problem solving sessions and progress report sessions. Specific open problems include questions regarding the combinatorial structures and topology (e.g., k^+-real face graphs, beyond upward planar graphs, sparse universal geometric graphs, local-crossing-critical graphs), the geometric representations (e.g., constrained outer string graphs, rerouting curves on surface), and applications. The details of the invited talks and progress reports from each working groups are included in this report.
Cite as

Vida Dujmović, Seok-Hee Hong, Michael Kaufmann, János Pach, and Henry Förster. Beyond-Planar Graphs: Models, Structures and Geometric Representations (Dagstuhl Seminar 24062). In Dagstuhl Reports, Volume 14, Issue 2, pp. 71-94, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{dujmovic_et_al:DagRep.14.2.71,
  author =	{Dujmovi\'{c}, Vida and Hong, Seok-Hee and Kaufmann, Michael and Pach, J\'{a}nos and F\"{o}rster, Henry},
  title =	{{Beyond-Planar Graphs: Models, Structures and Geometric Representations (Dagstuhl Seminar 24062)}},
  pages =	{71--94},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{14},
  number =	{2},
  editor =	{Dujmovi\'{c}, Vida and Hong, Seok-Hee and Kaufmann, Michael and Pach, J\'{a}nos and F\"{o}rster, Henry},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.14.2.71},
  URN =		{urn:nbn:de:0030-drops-204999},
  doi =		{10.4230/DagRep.14.2.71},
  annote =	{Keywords: Combinatorial geometry, Graph algorithm, Graph drawing, Graph theory, Network visualization}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.53
On Compact RAC Drawings

Authors: Henry Förster and Michael Kaufmann

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
We present new bounds for the required area of Right Angle Crossing (RAC) drawings for complete graphs, i.e. drawings where any two crossing edges are perpendicular to each other. First, we improve upon results by Didimo et al. [Walter Didimo et al., 2011] and Di Giacomo et al. [Emilio Di Giacomo et al., 2011] by showing how to compute a RAC drawing with three bends per edge in cubic area. We also show that quadratic area can be achieved when allowing eight bends per edge in general or with three bends per edge for p-partite graphs. As a counterpart, we prove that in general quadratic area is not sufficient for RAC drawings with three bends per edge.
Cite as

Henry Förster and Michael Kaufmann. On Compact RAC Drawings. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 53:1-53:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{forster_et_al:LIPIcs.ESA.2020.53,
  author =	{F\"{o}rster, Henry and Kaufmann, Michael},
  title =	{{On Compact RAC Drawings}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{53:1--53:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.53},
  URN =		{urn:nbn:de:0030-drops-129192},
  doi =		{10.4230/LIPIcs.ESA.2020.53},
  annote =	{Keywords: RAC drawings, visualization of dense graphs, compact drawings}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2020.21
Drawing Graphs with Circular Arcs and Right-Angle Crossings

Authors: Steven Chaplick, Henry Förster, Myroslav Kryven, and Alexander Wolff

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
In a RAC drawing of a graph, vertices are represented by points in the plane, adjacent vertices are connected by line segments, and crossings must form right angles. Graphs that admit such drawings are RAC graphs. RAC graphs are beyond-planar graphs and have been studied extensively. In particular, it is known that a RAC graph with n vertices has at most 4n-10 edges. We introduce a superclass of RAC graphs, which we call arc-RAC graphs. A graph is arc-RAC if it admits a drawing where edges are represented by circular arcs and crossings form right angles. We provide a Turán-type result showing that an arc-RAC graph with n vertices has at most 14n-12 edges and that there are n-vertex arc-RAC graphs with 4.5n - O(√n) edges.
Cite as

Steven Chaplick, Henry Förster, Myroslav Kryven, and Alexander Wolff. Drawing Graphs with Circular Arcs and Right-Angle Crossings. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chaplick_et_al:LIPIcs.SWAT.2020.21,
  author =	{Chaplick, Steven and F\"{o}rster, Henry and Kryven, Myroslav and Wolff, Alexander},
  title =	{{Drawing Graphs with Circular Arcs and Right-Angle Crossings}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.21},
  URN =		{urn:nbn:de:0030-drops-122687},
  doi =		{10.4230/LIPIcs.SWAT.2020.21},
  annote =	{Keywords: circular arcs, right-angle crossings, edge density, charging argument}
}
Document
DOI: 10.4230/LIPIcs.FUN.2016.6
Algorithms and Insights for RaceTrack

Authors: Michael A. Bekos, Till Bruckdorfer, Henry Förster, Michael Kaufmann, Simon Poschenrieder, and Thomas Stüber

Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)

Abstract
We discuss algorithmic issues on the well-known paper-and-pencil game RaceTrack. On a very simple track called Indianapolis, we introduce the problem and simple approaches, that will be gradually refined. We present and experimentally evaluate efficient algorithms for single player scenarios. We also consider a variant where the parts of the track are known as soon as they become visible during the race.
Cite as

Michael A. Bekos, Till Bruckdorfer, Henry Förster, Michael Kaufmann, Simon Poschenrieder, and Thomas Stüber. Algorithms and Insights for RaceTrack. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bekos_et_al:LIPIcs.FUN.2016.6,
  author =	{Bekos, Michael A. and Bruckdorfer, Till and F\"{o}rster, Henry and Kaufmann, Michael and Poschenrieder, Simon and St\"{u}ber, Thomas},
  title =	{{Algorithms and Insights for RaceTrack}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Demaine, Erik D. and Grandoni, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.6},
  URN =		{urn:nbn:de:0030-drops-58818},
  doi =		{10.4230/LIPIcs.FUN.2016.6},
  annote =	{Keywords: Racetrack, State-graph, complexity}
}
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