Search Results

Documents authored by Chimani, Markus

Document
DOI: 10.4230/LIPIcs.GD.2024.13
The Price of Upwardness

Authors: Patrizio Angelini, Therese Biedl, Markus Chimani, Sabine Cornelsen, Giordano Da Lozzo, Seok-Hee Hong, Giuseppe Liotta, Maurizio Patrignani, Sergey Pupyrev, Ignaz Rutter, and Alexander Wolff

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

Abstract
Not every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyond planarity by considering upward k-planar drawings of DAGs in which the edges are monotonically increasing in a common direction and every edge is crossed at most k times for some integer k ≥ 1. We show that the number of crossings per edge in a monotone drawing is in general unbounded for the class of bipartite outerplanar, cubic, or bounded pathwidth DAGs. However, it is at most two for outerpaths and it is at most quadratic in the bandwidth in general. From the computational point of view, we prove that upward-k-planarity testing is NP-complete already for k = 1 and even for restricted instances for which upward planarity testing is polynomial. On the positive side, we can decide in linear time whether a single-source DAG admits an upward 1-planar drawing in which all vertices are incident to the outer face.
Cite as

Patrizio Angelini, Therese Biedl, Markus Chimani, Sabine Cornelsen, Giordano Da Lozzo, Seok-Hee Hong, Giuseppe Liotta, Maurizio Patrignani, Sergey Pupyrev, Ignaz Rutter, and Alexander Wolff. The Price of Upwardness. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{angelini_et_al:LIPIcs.GD.2024.13,
  author =	{Angelini, Patrizio and Biedl, Therese and Chimani, Markus and Cornelsen, Sabine and Da Lozzo, Giordano and Hong, Seok-Hee and Liotta, Giuseppe and Patrignani, Maurizio and Pupyrev, Sergey and Rutter, Ignaz and Wolff, Alexander},
  title =	{{The Price of Upwardness}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{13:1--13:20},
  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.13},
  URN =		{urn:nbn:de:0030-drops-212977},
  doi =		{10.4230/LIPIcs.GD.2024.13},
  annote =	{Keywords: upward drawings, beyond planarity, upward k-planarity, upward outer-1-planarity}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.33
Crossing Numbers of Beyond Planar Graphs Re-Revisited: A Framework Approach

Authors: Markus Chimani, Torben Donzelmann, Nick Kloster, Melissa Koch, Jan-Jakob Völlering, and Mirko H. Wagner

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

Abstract
Beyond planarity concepts (prominent examples include k-planarity or fan-planarity) apply certain restrictions on the allowed patterns of crossings in drawings. It is natural to ask, how much the number of crossings may increase over the traditional (unrestricted) crossing number. Previous approaches to bound such ratios, e.g. [Markus Chimani et al., 2022; Nathan van Beusekom et al., 2022], require very specialized constructions and arguments for each considered beyond planarity concept, and mostly only yield asymptotically non-tight bounds. We propose a very general proof framework that allows us to obtain asymptotically tight bounds, and where the concept-specific parts of the proof typically boil down to a couple of lines. We show the strength of our approach by giving improved or first bounds for several beyond planarity concepts.
Cite as

Markus Chimani, Torben Donzelmann, Nick Kloster, Melissa Koch, Jan-Jakob Völlering, and Mirko H. Wagner. Crossing Numbers of Beyond Planar Graphs Re-Revisited: A Framework Approach. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chimani_et_al:LIPIcs.GD.2024.33,
  author =	{Chimani, Markus and Donzelmann, Torben and Kloster, Nick and Koch, Melissa and V\"{o}llering, Jan-Jakob and Wagner, Mirko H.},
  title =	{{Crossing Numbers of Beyond Planar Graphs Re-Revisited: A Framework Approach}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{33:1--33: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.33},
  URN =		{urn:nbn:de:0030-drops-213175},
  doi =		{10.4230/LIPIcs.GD.2024.33},
  annote =	{Keywords: Beyond planarity, crossing number, crossing ratio, proof framework}
}
Document
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2024.44
Graph-Drawing Supported Identification of Influential Students at Schools (Poster Abstract)

Authors: Markus Chimani, Lea Kröger, Juliane Liedtke, Jonah Mevert, Maor Shani, and Maarten van Zalk

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

Abstract
We consider the real-world problem of identifying a set of "influential" students at schools for a workshop on tolerance. We report on a tool that visualizes the networks of social connections between students, identifies sets of influential students, and lets one explore and understand the solution space with a focus on usability for teachers who are untrained in network analysis.
Cite as

Markus Chimani, Lea Kröger, Juliane Liedtke, Jonah Mevert, Maor Shani, and Maarten van Zalk. Graph-Drawing Supported Identification of Influential Students at Schools (Poster Abstract). In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 44:1-44:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chimani_et_al:LIPIcs.GD.2024.44,
  author =	{Chimani, Markus and Kr\"{o}ger, Lea and Liedtke, Juliane and Mevert, Jonah and Shani, Maor and van Zalk, Maarten},
  title =	{{Graph-Drawing Supported Identification of Influential Students at Schools}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{44:1--44: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.44},
  URN =		{urn:nbn:de:0030-drops-213282},
  doi =		{10.4230/LIPIcs.GD.2024.44},
  annote =	{Keywords: social network tool, force-directed graph drawing, group centrality}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.30
Exact Minimum Weight Spanners via Column Generation

Authors: Fritz Bökler, Markus Chimani, Henning Jasper, and Mirko H. Wagner

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
Given a weighted graph G, a minimum weight α-spanner is a least-weight subgraph H ⊆ G that preserves minimum distances between all node pairs up to a factor of α. There are many results on heuristics and approximation algorithms, including a recent investigation of their practical performance [Markus Chimani and Finn Stutzenstein, 2022]. Exact approaches, in contrast, have long been denounced as impractical: The first exact ILP (integer linear program) method [Sigurd and Zachariasen, 2004] from 2004 is based on a model with exponentially many path variables, solved via column generation. A second approach [Ahmed et al., 2019], modeling via arc-based multicommodity flow, was presented in 2019. In both cases, only graphs with 40-100 nodes were reported to be solvable. In this paper, we briefly report on a theoretical comparison between these two models from a polyhedral point of view, and then concentrate on improvements and engineering aspects. We evaluate their performance in a large-scale empirical study. We report that our tuned column generation approach, based on multicriteria shortest path computations, is able to solve instances with over 16 000 nodes within 13 min. Furthermore, now knowing optimal solutions for larger graphs, we are able to investigate the quality of the strongest known heuristic on reasonably sized instances for the first time.
Cite as

Fritz Bökler, Markus Chimani, Henning Jasper, and Mirko H. Wagner. Exact Minimum Weight Spanners via Column Generation. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bokler_et_al:LIPIcs.ESA.2024.30,
  author =	{B\"{o}kler, Fritz and Chimani, Markus and Jasper, Henning and Wagner, Mirko H.},
  title =	{{Exact Minimum Weight Spanners via Column Generation}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{30:1--30:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.30},
  URN =		{urn:nbn:de:0030-drops-211012},
  doi =		{10.4230/LIPIcs.ESA.2024.30},
  annote =	{Keywords: Graph spanners, ILP, algorithm engineering, experimental study}
}
Document
DOI: 10.4230/LIPIcs.SAND.2023.14
Multistage Shortest Path: Instances and Practical Evaluation

Authors: Markus Chimani and Niklas Troost

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)

Abstract
A multistage graph problem is a generalization of a traditional graph problem where, instead of a single input graph, we consider a sequence of graphs. We ask for a sequence of solutions, one for each input graph, such that consecutive solutions are as similar as possible. There are several theoretical results on different multistage problems and their complexities, as well as FPT and approximation algorithms. However, there is a severe lack of experimental validation and resulting feedback. Not only are there no algorithmic experiments in literature, we do not even know of any strong set of multistage benchmark instances. In this paper we want to improve on this situation. We consider the natural problem of multistage shortest path (MSP). First, we propose a rich benchmark set, ranging from synthetic to real-world data, and discuss relevant aspects to ensure non-trivial instances, which is a surprisingly delicate task. Secondly, we present an explorative study on heuristic, approximate, and exact algorithms for the MSP problem from a practical point of view. Our practical findings also inform theoretical research in arguing sensible further directions. For example, based on our study we propose to focus on algorithms for multistage instances that do not rely on 2-stage oracles.
Cite as

Markus Chimani and Niklas Troost. Multistage Shortest Path: Instances and Practical Evaluation. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chimani_et_al:LIPIcs.SAND.2023.14,
  author =	{Chimani, Markus and Troost, Niklas},
  title =	{{Multistage Shortest Path: Instances and Practical Evaluation}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{14:1--14:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.14},
  URN =		{urn:nbn:de:0030-drops-179507},
  doi =		{10.4230/LIPIcs.SAND.2023.14},
  annote =	{Keywords: Multistage Graphs, Shortest Paths, Experiments}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.37
Spanner Approximations in Practice

Authors: Markus Chimani and Finn Stutzenstein

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
A multiplicative α-spanner H is a subgraph of G = (V,E) with the same vertices and fewer edges that preserves distances up to the factor α, i.e., d_H(u,v) ≤ α⋅ d_G(u,v) for all vertices u, v. While many algorithms have been developed to find good spanners in terms of approximation guarantees, no experimental studies comparing different approaches exist. We implemented a rich selection of those algorithms and evaluate them on a variety of instances regarding, e.g., their running time, sparseness, lightness, and effective stretch.
Cite as

Markus Chimani and Finn Stutzenstein. Spanner Approximations in Practice. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chimani_et_al:LIPIcs.ESA.2022.37,
  author =	{Chimani, Markus and Stutzenstein, Finn},
  title =	{{Spanner Approximations in Practice}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{37:1--37:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.37},
  URN =		{urn:nbn:de:0030-drops-169750},
  doi =		{10.4230/LIPIcs.ESA.2022.37},
  annote =	{Keywords: Graph spanners, experimental study, algorithm engineering}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.30
Stronger ILPs for the Graph Genus Problem

Authors: Markus Chimani and Tilo Wiedera

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

Abstract
The minimum genus of a graph is an important question in graph theory and a key ingredient in several graph algorithms. However, its computation is NP-hard and turns out to be hard even in practice. Only recently, the first non-trivial approach - based on SAT and ILP (integer linear programming) models - has been presented, but it is unable to successfully tackle graphs of genus larger than 1 in practice. Herein, we show how to improve the ILP formulation. The crucial ingredients are two-fold. First, we show that instead of modeling rotation schemes explicitly, it suffices to optimize over partitions of the (bidirected) arc set A of the graph. Second, we exploit the cycle structure of the graph, explicitly mapping short closed walks on A to faces in the embedding. Besides the theoretical advantages of our models, we show their practical strength by a thorough experimental evaluation. Contrary to the previous approach, we are able to quickly solve many instances of genus > 1.
Cite as

Markus Chimani and Tilo Wiedera. Stronger ILPs for the Graph Genus Problem. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chimani_et_al:LIPIcs.ESA.2019.30,
  author =	{Chimani, Markus and Wiedera, Tilo},
  title =	{{Stronger ILPs for the Graph Genus Problem}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{30:1--30:15},
  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.30},
  URN =		{urn:nbn:de:0030-drops-111511},
  doi =		{10.4230/LIPIcs.ESA.2019.30},
  annote =	{Keywords: algorithm engineering, genus, integer linear programming}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.19
Cycles to the Rescue! Novel Constraints to Compute Maximum Planar Subgraphs Fast

Authors: Markus Chimani and Tilo Wiedera

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
The NP-hard Maximum Planar Subgraph problem asks for a planar subgraph H of a given graph G such that H has maximum edge cardinality. For more than two decades, the only known non-trivial exact algorithm was based on integer linear programming and Kuratowski's famous planarity criterion. We build upon this approach and present new constraint classes - together with a lifting of the polyhedron - to obtain provably stronger LP-relaxations, and in turn faster algorithms in practice. The new constraints take Euler's polyhedron formula as a starting point and combine it with considering cycles in G. This paper discusses both the theoretical as well as the practical sides of this strengthening.
Cite as

Markus Chimani and Tilo Wiedera. Cycles to the Rescue! Novel Constraints to Compute Maximum Planar Subgraphs Fast. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chimani_et_al:LIPIcs.ESA.2018.19,
  author =	{Chimani, Markus and Wiedera, Tilo},
  title =	{{Cycles to the Rescue! Novel Constraints to Compute Maximum Planar Subgraphs Fast}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah 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.2018.19},
  URN =		{urn:nbn:de:0030-drops-94829},
  doi =		{10.4230/LIPIcs.ESA.2018.19},
  annote =	{Keywords: algorithm engineering, graph algorithms, integer linear programming, maximum planar subgraph}
}
Document
DOI: 10.4230/LIPIcs.SEA.2018.22
Exact Algorithms for the Maximum Planar Subgraph Problem: New Models and Experiments

Authors: Markus Chimani, Ivo Hedtke, and Tilo Wiedera

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

Abstract
Given a graph G, the NP-hard Maximum Planar Subgraph problem asks for a planar subgraph of G with the maximum number of edges. The only known non-trivial exact algorithm utilizes Kuratowski's famous planarity criterion and can be formulated as an integer linear program (ILP) or a pseudo-boolean satisfiability problem (PBS). We examine three alternative characterizations of planarity regarding their applicability to model maximum planar subgraphs. For each, we consider both ILP and PBS variants, investigate diverse formulation aspects, and evaluate their practical performance.
Cite as

Markus Chimani, Ivo Hedtke, and Tilo Wiedera. Exact Algorithms for the Maximum Planar Subgraph Problem: New Models and Experiments. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chimani_et_al:LIPIcs.SEA.2018.22,
  author =	{Chimani, Markus and Hedtke, Ivo and Wiedera, Tilo},
  title =	{{Exact Algorithms for the Maximum Planar Subgraph Problem: New Models and Experiments}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{22:1--22:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.22},
  URN =		{urn:nbn:de:0030-drops-89572},
  doi =		{10.4230/LIPIcs.SEA.2018.22},
  annote =	{Keywords: maximum planar subgraph, integer linear programming, pseudo boolean satisfiability, graph drawing, algorithm engineering}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.13
Crossing Number for Graphs with Bounded~Pathwidth

Authors: Therese Biedl, Markus Chimani, Martin Derka, and Petra Mutzel

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.ESA.2016.29
An ILP-based Proof System for the Crossing Number Problem

Authors: Markus Chimani and Tilo Wiedera

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
Formally, approaches based on mathematical programming are able to find provably optimal solutions. However, the demands on a verifiable formal proof are typically much higher than the guarantees we can sensibly attribute to implementations of mathematical programs. We consider this in the context of the crossing number problem, one of the most prominent problems in topological graph theory. The problem asks for the minimum number of edge crossings in any drawing of a given graph. Graph-theoretic proofs for this problem are known to be notoriously hard to obtain. At the same time, proofs even for very specific graphs are often of interest in crossing number research, as they can, e.g., form the basis for inductive proofs. We propose a system to automatically generate a formal proof based on an ILP computation. Such a proof is (relatively) easily verifiable, and does not require the understanding of any complex ILP codes. As such, we hope our proof system may serve as a showcase for the necessary steps and central design goals of how to establish formal proof systems based on mathematical programming formulations.
Cite as

Markus Chimani and Tilo Wiedera. An ILP-based Proof System for the Crossing Number Problem. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chimani_et_al:LIPIcs.ESA.2016.29,
  author =	{Chimani, Markus and Wiedera, Tilo},
  title =	{{An ILP-based Proof System for the Crossing Number Problem}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{29:1--29:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.29},
  URN =		{urn:nbn:de:0030-drops-63803},
  doi =		{10.4230/LIPIcs.ESA.2016.29},
  annote =	{Keywords: automatic formal proof, crossing number, integer linear programming}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.30
Inserting Multiple Edges into a Planar Graph

Authors: Markus Chimani and Petr Hlinený

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
Let G be a connected planar (but not yet embedded) graph and F a set of additional edges not in G. The multiple edge insertion problem (MEI) asks for a drawing of G+F with the minimum number of pairwise edge crossings, such that the subdrawing of G is plane. An optimal solution to this problem is known to approximate the crossing number of the graph G+F. Finding an exact solution to MEI is NP-hard for general F, but linear time solvable for the special case of |F|=1 [Gutwenger et al, SODA 2001/Algorithmica] and polynomial time solvable when all of F are incident to a new vertex [Chimani et al, SODA 2009]. The complexity for general F but with constant k=|F| was open, but algorithms both with relative and absolute approximation guarantees have been presented [Chuzhoy et al, SODA 2011], [Chimani-Hlineny, ICALP 2011]. We show that the problem is fixed parameter tractable (FPT) in k for biconnected G, or if the cut vertices of G have bounded degrees. We give the first exact algorithm for this problem; it requires only O(|V(G)|) time for any constant k.
Cite as

Markus Chimani and Petr Hlinený. Inserting Multiple Edges into a Planar Graph. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chimani_et_al:LIPIcs.SoCG.2016.30,
  author =	{Chimani, Markus and Hlinen\'{y}, Petr},
  title =	{{Inserting Multiple Edges into a Planar Graph}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{30:1--30:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.30},
  URN =		{urn:nbn:de:0030-drops-59223},
  doi =		{10.4230/LIPIcs.SoCG.2016.30},
  annote =	{Keywords: crossing number, edge insertion, parameterized complexity, path homotopy, funnel algorithm}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.238
Network Design Problems with Bounded Distances via Shallow-Light Steiner Trees

Authors: Markus Chimani and Joachim Spoerhase

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
In a directed graph G with non-correlated edge lengths and costs, the network design problem with bounded distances asks for a cost-minimal spanning subgraph subject to a length bound for all node pairs. We give a bi-criteria (2+\varepsilon,O(n^{0.5+\varepsilon}))-approximation for this problem. This improves on the currently best known linear approximation bound, at the cost of violating the distance bound by a factor of at most 2+\varepsilon. In the course of proving this result, the related problem of directed shallow-light Steiner trees arises as a subproblem. In the context of directed graphs, approximations to this problem have been elusive. We present the first non-trivial result by proposing a (1+\varepsilon,O(|R|^{\varepsilon}))-ap\-proximation, where R is the set of terminals. Finally, we show how to apply our results to obtain an (\alpha+\varepsilon,O(n^{0.5+\varepsilon}))-approximation for light-weight directed \alpha-spanners. For this, no non-trivial approximation algorithm has been known before. All running times depends on n and \varepsilon and are polynomial in n for any fixed \varepsilon>0.
Cite as

Markus Chimani and Joachim Spoerhase. Network Design Problems with Bounded Distances via Shallow-Light Steiner Trees. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 238-248, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{chimani_et_al:LIPIcs.STACS.2015.238,
  author =	{Chimani, Markus and Spoerhase, Joachim},
  title =	{{Network Design Problems with Bounded Distances via Shallow-Light Steiner Trees}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{238--248},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.238},
  URN =		{urn:nbn:de:0030-drops-49170},
  doi =		{10.4230/LIPIcs.STACS.2015.238},
  annote =	{Keywords: network design, approximation algorithm, shallow-light spanning trees, spanners}
}
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 Imprint Privacy Contact