Document

**Published in:** LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Preprocessing is an important ingredient for solving the maximum cut problem to optimality on real-world graphs. In our work, we derive a new framework for data reduction rules based on vertex separators. Vertex separators are sets of vertices, whose removal increases the number of connected components of a graph. Certain small separators can be found in linear time, allowing for an efficient combination of our framework with existing data reduction rules. Additionally, we complement known data reduction rules for triangles with a new one.
In our computational experiments on established benchmark instances, we clearly show the effectiveness and efficiency of our proposed data reduction techniques. The resulting graphs are significantly smaller than in earlier studies and sometimes no vertex is left, so preprocessing has fully solved the instance to optimality. The introduced techniques are also shown to offer significant speedup potential for an exact state-of-the-art solver and to help a state-of-the-art heuristic to produce solutions of higher quality.

Jonas Charfreitag, Christine Dahn, Michael Kaibel, Philip Mayer, Petra Mutzel, and Lukas Schürmann. Separator Based Data Reduction for the Maximum Cut Problem. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 4:1-4:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{charfreitag_et_al:LIPIcs.SEA.2024.4, author = {Charfreitag, Jonas and Dahn, Christine and Kaibel, Michael and Mayer, Philip and Mutzel, Petra and Sch\"{u}rmann, Lukas}, title = {{Separator Based Data Reduction for the Maximum Cut Problem}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {4:1--4:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.4}, URN = {urn:nbn:de:0030-drops-203698}, doi = {10.4230/LIPIcs.SEA.2024.4}, annote = {Keywords: Data Reduction, Maximum Cut, Vertex Separators} }

Document

**Published in:** LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

The flip distance for two triangulations of a point set is defined as the smallest number of edge flips needed to transform one triangulation into another, where an edge flip is the act of replacing an edge of a triangulation by a different edge such that the result remains a triangulation.
We adapt and engineer a sophisticated A* search algorithm acting on the so-called flip graph. In particular, we prove that previously proposed lower bounds for the flip distance form consistent heuristics for A* and show that they can be computed efficiently using dynamic algorithms. As an alternative approach, we present an integer linear program (ILP) for the flip distance problem.
We experimentally evaluate our approaches on a new real-world benchmark data set based on an application in geodesy, namely sea surface reconstruction. Our evaluation reveals that A* search consistently outperforms our ILP formulation as well as a naive baseline, which is bidirectional breadth-first search. In particular, the runtime of our approach improves upon the baseline by more than two orders of magnitude. Furthermore, our A* search successfully solves most of the considered sea surface instances with up to 41 points. This is a substantial improvement compared to the baseline, which struggles with subsets of the real-world data of size 25.
Lastly, to allow the consideration of global sea level data, we developed a decomposition-based heuristic for the flip distance. In our experiments it yields optimal flip distance values for most of the considered sea level data and it can be applied to large data sets due to its fast runtime.

Philip Mayer and Petra Mutzel. Engineering A* Search for the Flip Distance of Plane Triangulations. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 23:1-23:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mayer_et_al:LIPIcs.SEA.2024.23, author = {Mayer, Philip and Mutzel, Petra}, title = {{Engineering A* Search for the Flip Distance of Plane Triangulations}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {23:1--23:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.23}, URN = {urn:nbn:de:0030-drops-203887}, doi = {10.4230/LIPIcs.SEA.2024.23}, annote = {Keywords: Computational Geometry, Triangulations, Flip Distance, A-star Search, Integer Linear Programming} }

Document

**Published in:** LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

We apply state-of-the-art computational geometry methods to the problem of reconstructing a time-varying sea surface from tide gauge records. Our work builds on a recent article by Nitzke et al. (Computers & Geosciences, 157:104920, 2021) who have suggested to learn a triangulation D of a given set of tide gauge stations. The objective is to minimize the misfit of the piecewise linear surface induced by D to a reference surface that has been acquired with satellite altimetry. The authors restricted their search to k-order Delaunay (k-OD) triangulations and used an integer linear program in order to solve the resulting optimization problem.
In geometric terms, the input to our problem consists of two sets of points in ℝ² with elevations: a set 𝒮 that is to be triangulated, and a set ℛ of reference points. Intuitively, we define the error of a triangulation as the average vertical distance of a point in ℛ to the triangulated surface that is obtained by interpolating elevations of 𝒮 linearly in each triangle. Our goal is to find the triangulation of 𝒮 that has minimum error with respect to ℛ.
In our work, we prove that the minimum-error triangulation problem is NP-hard and cannot be approximated within any multiplicative factor in polynomial time unless P = NP. At the same time we show that the problem instances that occur in our application (considering sea level data from several hundreds of tide gauge stations worldwide) can be solved relatively fast using dynamic programming when restricted to k-OD triangulations for k ≤ 7. In particular, instances for which the number of connected components of the so-called k-OD fixed-edge graph is small can be solved within few seconds.

Anna Arutyunova, Anne Driemel, Jan-Henrik Haunert, Herman Haverkort, Jürgen Kusche, Elmar Langetepe, Philip Mayer, Petra Mutzel, and Heiko Röglin. Minimum-Error Triangulations for Sea Surface Reconstruction. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{arutyunova_et_al:LIPIcs.SoCG.2022.7, author = {Arutyunova, Anna and Driemel, Anne and Haunert, Jan-Henrik and Haverkort, Herman and Kusche, J\"{u}rgen and Langetepe, Elmar and Mayer, Philip and Mutzel, Petra and R\"{o}glin, Heiko}, title = {{Minimum-Error Triangulations for Sea Surface Reconstruction}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {7:1--7:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-227-3}, ISSN = {1868-8969}, year = {2022}, volume = {224}, editor = {Goaoc, Xavier and Kerber, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.7}, URN = {urn:nbn:de:0030-drops-160155}, doi = {10.4230/LIPIcs.SoCG.2022.7}, annote = {Keywords: Minimum-Error Triangulation, k-Order Delaunay Triangulations, Data dependent Triangulations, Sea Surface Reconstruction, fixed-Edge Graph} }

Document

Complete Volume

**Published in:** LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

LIPIcs, Volume 204, ESA 2021, Complete Volume

29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 1-1340, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Proceedings{mutzel_et_al:LIPIcs.ESA.2021, title = {{LIPIcs, Volume 204, ESA 2021, Complete Volume}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {1--1340}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus 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.2021}, URN = {urn:nbn:de:0030-drops-145808}, doi = {10.4230/LIPIcs.ESA.2021}, annote = {Keywords: LIPIcs, Volume 204, ESA 2021, Complete Volume} }

Document

Front Matter

**Published in:** LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Front Matter, Table of Contents, Preface, Conference Organization

29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{mutzel_et_al:LIPIcs.ESA.2021.0, author = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {0:i--0:xx}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus 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.2021.0}, URN = {urn:nbn:de:0030-drops-145816}, doi = {10.4230/LIPIcs.ESA.2021.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }

Document

Invited Talk

**Published in:** LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

The area of algorithmic data science provides new opportunities for researchers in the algorithmic community. In this paper we will see examples that demonstrate that algorithm engineering is the perfect basis for algorithmic data science. But there are also many open interesting questions for purely theoretically interested computer scientists. In my opinion, these opportunities should be taken because this will be fruitful for both areas, algorithmics as well as data sciences. I like to call for more participation in algorithmic data science by our community. Now we have the opportunity to shape this new emerging field.

Petra Mutzel. Algorithmic Data Science (Invited Talk). In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{mutzel:LIPIcs.STACS.2019.3, author = {Mutzel, Petra}, title = {{Algorithmic Data Science}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {3:1--3:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.3}, URN = {urn:nbn:de:0030-drops-102425}, doi = {10.4230/LIPIcs.STACS.2019.3}, annote = {Keywords: Algorithmic Data Science, Graph Similarity, Weisfeiler-Leman} }

Document

**Published in:** LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

The largest common embeddable subtree problem asks for the largest possible tree embeddable into two input trees and generalizes the classical maximum common subtree problem. Several variants of the problem in labeled and unlabeled rooted trees have been studied, e.g., for the comparison of evolutionary trees. We consider a generalization, where the sought embedding is maximal with regard to a weight function on pairs of labels. We support rooted and unrooted trees with vertex and edge labels as well as distance penalties for skipping vertices. This variant is important for many applications such as the comparison of chemical structures and evolutionary trees. Our algorithm computes the solution from a series of bipartite matching instances, which are solved efficiently by exploiting their structural relation and imbalance. Our analysis shows that our approach improves or matches the running time of the formally best algorithms for several problem variants. Specifically, we obtain a running time of O(|T| |T'|Delta) for two rooted or unrooted trees T and T', where Delta=min{Delta(T),Delta(T')} with Delta(X) the maximum degree of X. If the weights are integral and at most C, we obtain a running time of O(|T| |T'|sqrt Delta log (C min{|T|,|T'|})) for rooted trees.

Andre Droschinsky, Nils M. Kriege, and Petra Mutzel. Largest Weight Common Subtree Embeddings with Distance Penalties. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 54:1-54:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{droschinsky_et_al:LIPIcs.MFCS.2018.54, author = {Droschinsky, Andre and Kriege, Nils M. and Mutzel, Petra}, title = {{Largest Weight Common Subtree Embeddings with Distance Penalties}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {54:1--54:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.54}, URN = {urn:nbn:de:0030-drops-96367}, doi = {10.4230/LIPIcs.MFCS.2018.54}, annote = {Keywords: maximum common subtree, largest embeddable subtree, topological embedding, maximum weight matching, subtree homeomorphism} }

Document

**Published in:** LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

The crossing number is the smallest number of pairwise edge crossings when drawing a graph into the plane. There are only very few graph classes for which the exact crossing number is known or for which there at least exist constant approximation ratios. Furthermore, up to now, general crossing number computations have never been successfully tackled using bounded width of graph decompositions, like treewidth or pathwidth.
In this paper, we for the first time show that crossing number is tractable (even in linear time) for maximal graphs of bounded pathwidth 3. The technique also shows that the crossing number and the rectilinear (a.k.a. straight-line) crossing number are identical for this graph class, and that we require only an O(n)xO(n)-grid to achieve such a drawing.
Our techniques can further be extended to devise a 2-approximation for general graphs with pathwidth 3, and a 4w^3-approximation for maximal graphs of pathwidth w. This is a constant approximation for bounded pathwidth graphs.

Therese Biedl, Markus Chimani, Martin Derka, and Petra Mutzel. Crossing Number for Graphs with Bounded~Pathwidth. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.ISAAC.2017.13, author = {Biedl, Therese and Chimani, Markus and Derka, Martin and Mutzel, Petra}, title = {{Crossing Number for Graphs with Bounded\textasciitildePathwidth}}, booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)}, pages = {13:1--13:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-054-5}, ISSN = {1868-8969}, year = {2017}, volume = {92}, editor = {Okamoto, Yoshio and Tokuyama, Takeshi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.13}, URN = {urn:nbn:de:0030-drops-82570}, doi = {10.4230/LIPIcs.ISAAC.2017.13}, annote = {Keywords: Crossing Number, Graphs with Bounded Pathwidth} }

Document

**Published in:** LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

We present an algorithm for the k shortest simple path problem on weighted directed graphs (kSSP) that is based on Eppstein’s algorithm for a similar problem in which paths are allowed to contain cycles. In contrast to most other algorithms for kSSP, ours is not based on Yen's algorithm [Networks, 1971] and does not solve replacement path problems. Its worst-case running time is on par with state-of-the-art algorithms for kSSP. Using our algorithm, one may find O(m) simple paths with a single shortest path tree computation and O(n+m) additional time per path in well-behaved cases, where n is the number of nodes and m is the number of edges. Our computational results show that on random graphs and large road networks, these well-behaved cases are quite common and our algorithm is faster than existing algorithms by an order of magnitude.

Denis Kurz and Petra Mutzel. A Sidetrack-Based Algorithm for Finding the k Shortest Simple Paths in a Directed Graph. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 49:1-49:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kurz_et_al:LIPIcs.ISAAC.2016.49, author = {Kurz, Denis and Mutzel, Petra}, title = {{A Sidetrack-Based Algorithm for Finding the k Shortest Simple Paths in a Directed Graph}}, booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)}, pages = {49:1--49:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-026-2}, ISSN = {1868-8969}, year = {2016}, volume = {64}, editor = {Hong, Seok-Hee}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.49}, URN = {urn:nbn:de:0030-drops-68199}, doi = {10.4230/LIPIcs.ISAAC.2016.49}, annote = {Keywords: directed graph, k-best, shortest path, simple path, weighted graph} }

Document

**Published in:** LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

The maximum common subtree isomorphism problem asks for the largest possible isomorphism between subtrees of two given input trees. This problem is a natural restriction of the maximum common subgraph problem, which is NP-hard in general graphs. Confining to trees renders polynomial time algorithms possible and is of fundamental importance for approaches on more general graph classes.Various variants of this problem in trees have been intensively studied. We consider the general case, where trees are neither rooted nor ordered and the isomorphism is maximum w.r.t. a weight function on the mapped vertices and edges. For trees of order n and maximum degree Delta our algorithm achieves a running time of O(n^2*Delta) by exploiting the structure of the matching instances arising as subproblems. Thus our algorithm outperforms the best previously known approaches. No faster algorithm is possible for trees of bounded degree and for trees of unbounded degree we show that a further reduction of the running time would directly improve the best known approach to the assignment problem. Combining a polynomial-delay algorithm for the enumeration of all maximum common subtree isomorphisms with central ideas of our new algorithm leads to an improvement of its running time from O(n^6+T*n^2) to O(n^3+T*n*Delta), where n is the order of the larger tree, T is the number of different solutions, and Delta is the minimum of the maximum degrees of the input trees. Our theoretical results are supplemented by an experimental evaluation on synthetic and real-world instances.

Andre Droschinsky, Nils M. Kriege, and Petra Mutzel. Faster Algorithms for the Maximum Common Subtree Isomorphism Problem. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{droschinsky_et_al:LIPIcs.MFCS.2016.33, author = {Droschinsky, Andre and Kriege, Nils M. and Mutzel, Petra}, title = {{Faster Algorithms for the Maximum Common Subtree Isomorphism Problem}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {33:1--33:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.33}, URN = {urn:nbn:de:0030-drops-64475}, doi = {10.4230/LIPIcs.MFCS.2016.33}, annote = {Keywords: MCS, maximum common subtree, enumeration algorithms, maximum weight bipartite matchings} }

Document

**Published in:** Dagstuhl Reports, Volume 1, Issue 5 (2011)

This report documents the program and the outcomes of Dagstuhl Seminar 11191
``Graph Drawing with Algorithm Engineering Methods''. We summarize the talks,
open problems, and working group discussions.

Camil Demetrescu, Michael Kaufmann, Stephen Kobourov, and Petra Mutzel. Graph Drawing with Algorithm Engineering Methods (Dagstuhl Seminar 11191). In Dagstuhl Reports, Volume 1, Issue 5, pp. 47-60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{demetrescu_et_al:DagRep.1.5.47, author = {Demetrescu, Camil and Kaufmann, Michael and Kobourov, Stephen and Mutzel, Petra}, title = {{Graph Drawing with Algorithm Engineering Methods (Dagstuhl Seminar 11191)}}, pages = {47--60}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2011}, volume = {1}, number = {5}, editor = {Demetrescu, Camil and Kaufmann, Michael and Kobourov, Stephen and Mutzel, Petra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.5.47}, URN = {urn:nbn:de:0030-drops-32046}, doi = {10.4230/DagRep.1.5.47}, annote = {Keywords: Algorithm Engineering, Graph Drawing} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 10261, Algorithm Engineering (2010)

From June 27 to July 2, the Dagstuhl Seminar 10261 ``Algorithm Engineering '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics.
During the seminar, several participants presented their current
research, and ongoing work and open problems were discussed. Abstracts of
the presentations given during the seminar as well as abstracts of
seminar results and ideas are put together in this paper. The first section
describes the seminar topics and goals in general.
Links to extended abstracts or full papers are provided, if available.

Giuseppe F. Italiano, David S. Johnson, Petra Mutzel, and Peter Sanders. 10261 Abstracts Collection – Algorithm Engineering. In Algorithm Engineering. Dagstuhl Seminar Proceedings, Volume 10261, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{italiano_et_al:DagSemProc.10261.1, author = {Italiano, Giuseppe F. and Johnson, David S. and Mutzel, Petra and Sanders, Peter}, title = {{10261 Abstracts Collection – Algorithm Engineering}}, booktitle = {Algorithm Engineering}, pages = {1--10}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {10261}, editor = {Giuseppe F. Italiano and David S. Johnson and Petra Mutzel and Peter Sanders}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10261.1}, URN = {urn:nbn:de:0030-drops-28179}, doi = {10.4230/DagSemProc.10261.1}, annote = {Keywords: Experimental algorithmics, Game theory, Parallel and distributed algorithms, Multi-core} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 10261, Algorithm Engineering (2010)

Algorithm engineering (AE) consists of the design,
theoretical analysis, implementation, and experimental
evaluation of algorithms, with the aim of bridging the gap between
theory and practice in the area of algorithms. In the last decade,
this approach to algorithmic research has gained increasing
attention.
The aim of this seminar was to bring together researchers with
different backgrounds, e.g., from combinatorial optimization, algorithmic
theory, and algorithm engineering, in order to strengthen and foster
collaborations in the area of algorithm engineering and to identify
key research directions for the future.

Giuseppe F. Italiano, David S. Johnson, Petra Mutzel, and Peter Sanders. 10261 Executive Summary – Algorithm Engineering. In Algorithm Engineering. Dagstuhl Seminar Proceedings, Volume 10261, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{italiano_et_al:DagSemProc.10261.2, author = {Italiano, Giuseppe F. and Johnson, David S. and Mutzel, Petra and Sanders, Peter}, title = {{10261 Executive Summary – Algorithm Engineering}}, booktitle = {Algorithm Engineering}, pages = {1--2}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {10261}, editor = {Giuseppe F. Italiano and David S. Johnson and Petra Mutzel and Peter Sanders}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10261.2}, URN = {urn:nbn:de:0030-drops-27966}, doi = {10.4230/DagSemProc.10261.2}, annote = {Keywords: Experimental algorithmics, Game theory, Parallel and distributed algorithms, Multi-core} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 8191, Graph Drawing with Applications to Bioinformatics and Social Sciences (2008)

From May 4 to May 9, 2008, the Dagstuhl Seminar 08191 ``Graph Drawing with Applications to Bioinformatics and Social Sciences'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl.
During the seminar, several participants presented their current
research, and ongoing work and open problems were discussed. Abstracts of
the presentations given during the seminar as well as abstracts of
seminar results and ideas are put together in this paper. The first section
describes the seminar topics and goals in general.
Links to extended abstracts or full papers are provided, if available.

Stephen Borgatti, Stephen Kobourov, Oliver Kohlbacher, and Petra Mutzel. 08191 Abstracts Collection – Graph Drawing with Applications to Bioinformatics and Social Sciences. In Graph Drawing with Applications to Bioinformatics and Social Sciences. Dagstuhl Seminar Proceedings, Volume 8191, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{borgatti_et_al:DagSemProc.08191.1, author = {Borgatti, Stephen and Kobourov, Stephen and Kohlbacher, Oliver and Mutzel, Petra}, title = {{08191 Abstracts Collection – Graph Drawing with Applications to Bioinformatics and Social Sciences}}, booktitle = {Graph Drawing with Applications to Bioinformatics and Social Sciences}, pages = {1--10}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8191}, editor = {Stephen P. Borgatti and Stephen Kobourov and Oliver Kohlbacher and Petra Mutzel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08191.1}, URN = {urn:nbn:de:0030-drops-15547}, doi = {10.4230/DagSemProc.08191.1}, annote = {Keywords: Graph drawing, visualization, social sciences, bioinformatics} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 8191, Graph Drawing with Applications to Bioinformatics and Social Sciences (2008)

Graph drawing deals with the problem of communicating the structure of
relational data through diagrams, or drawings. The ability to represent
relational information in a graphical form is a powerful tool which allows
to perform analysis through visual exploration to find important patterns,
trends, and correlations. Real-world applications such as bioinformatics and
sociology pose challenges to the relational visualization because, e.g., semantic
information carried by the diagram has to be used for obtaining meaningful layouts and
application-specific drawing conventions need to be fulfilled. Moreover, the
underlying data often stems from huge data bases, but only a small fraction
shall be displayed at a time; the user interactively selects the data to be
displayed and explores the graph by expanding interesting and collapsing
irrelevant parts. This requires powerful graph exploration tools with
navigation capabilities that allow dynamic adaption of the graph layout in real
time. In this seminar we focused on the application of graph drawing in two
important application domains: bioinformatics and social sciences.
We brought together theoreticians and practitioners from these areas
and focused on problems concerning interaction with and navigation in large
and dynamic networks arising in these application areas;
During the seminar, we identified and defined open graph drawing problems
that are motivated by practical applications in the targeted application areas,
tackled selected open problems, formulated the findings as a first step to
the solution, and defined further research directions.

Stephen Borgatti, Stephen Kobourov, Oliver Kohlbacher, and Petra Mutzel. 08191 Executive Summary – Graph Drawing with Applications to Bioinformatics and Social Sciences. In Graph Drawing with Applications to Bioinformatics and Social Sciences. Dagstuhl Seminar Proceedings, Volume 8191, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{borgatti_et_al:DagSemProc.08191.2, author = {Borgatti, Stephen and Kobourov, Stephen and Kohlbacher, Oliver and Mutzel, Petra}, title = {{08191 Executive Summary – Graph Drawing with Applications to Bioinformatics and Social Sciences}}, booktitle = {Graph Drawing with Applications to Bioinformatics and Social Sciences}, pages = {1--3}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8191}, editor = {Stephen P. Borgatti and Stephen Kobourov and Oliver Kohlbacher and Petra Mutzel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08191.2}, URN = {urn:nbn:de:0030-drops-15523}, doi = {10.4230/DagSemProc.08191.2}, annote = {Keywords: Graph drawing, visualization, social sciences, bioinformatics} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 5191, Graph Drawing (2006)

From 08.05.05 to 13.05.05, the Dagstuhl Seminar 05191 ``Graph Drawing'' was held
in the International Conference and Research Center (IBFI), Schloss Dagstuhl.
During the seminar, several participants presented their current
research, and ongoing work and open problems were discussed. Abstracts of
the presentations given during the seminar as well as abstracts of
seminar results and ideas are put together in this paper. The first section
describes the seminar topics and goals in general.
Links to extended abstracts or full papers are provided, if available.

Michael Jünger, Petra Mutzel, and Stephen Kobourov. 05191 Abstracts Collection – Graph Drawing. In Graph Drawing. Dagstuhl Seminar Proceedings, Volume 5191, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{junger_et_al:DagSemProc.05191.1, author = {J\"{u}nger, Michael and Mutzel, Petra and Kobourov, Stephen}, title = {{05191 Abstracts Collection – Graph Drawing}}, booktitle = {Graph Drawing}, pages = {1--15}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {5191}, editor = {Michael J\"{u}nger and Stephen Kobourov and Petra Mutzel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05191.1}, URN = {urn:nbn:de:0030-drops-3485}, doi = {10.4230/DagSemProc.05191.1}, annote = {Keywords: Graph Drawing, Visualization, Layout Algorithms, Interactive Visualization} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 5191, Graph Drawing (2006)

This paper summarizes the topics, aims, and achievements of the Dagstuhl Seminar 05191 on Graph Drawing.

Michael Jünger, Stephen Kobourov, and Petra Mutzel. 05191 Executive Summary – Graph Drawing. In Graph Drawing. Dagstuhl Seminar Proceedings, Volume 5191, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{junger_et_al:DagSemProc.05191.2, author = {J\"{u}nger, Michael and Kobourov, Stephen and Mutzel, Petra}, title = {{05191 Executive Summary – Graph Drawing}}, booktitle = {Graph Drawing}, pages = {1--3}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {5191}, editor = {Michael J\"{u}nger and Stephen Kobourov and Petra Mutzel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05191.2}, URN = {urn:nbn:de:0030-drops-3420}, doi = {10.4230/DagSemProc.05191.2}, annote = {Keywords: Graph drawing} }