The Experts below are selected from a list of 25575 Experts worldwide ranked by ideXlab platform
Rolf Niedermeier - One of the best experts on this subject based on the ideXlab platform.
-
parameterized complexity exponential speed up for Planar Graph problems
Journal of Algorithms, 2004Co-Authors: Jochen Alber, Henning Fernau, Rolf NiedermeierAbstract:We discuss general techniques, centered around the "Layerwise Separation Property" (LSP) of a Planar Graph problem, that allow to develop algorithms with running time c√k|G|, given an instance G of a problem on Planar Graphs with parameter k. Problems having LSP include Planar VERTEX COVER. Planar INDEPENDENT SET, and Planar DOMINATING SET. Extensions of our speed-up technique to basically all fixed-parameter tractable Planar Graph problems are also exhibited. Moreover, we relate, e.g., the domination number or the vertex cover number, with the treewidth of a plane Graph.
-
parameterized complexity exponential speed up for Planar Graph problems
International Colloquium on Automata Languages and Programming, 2001Co-Authors: Jochen Alber, Henning Fernau, Rolf NiedermeierAbstract:A parameterized problem is fixed parameter tractable if it admits a solving algorithm whose running time on input instance (I, k) is f(k)ċ|I|α, where f is an arbitrary function depending only on k. Typically, f is some exponential function, e.g., f(k) = ck for constant c. We describe general techniques to obtain growth of the form f(k) = ck for a large variety of Planar Graph problems. The key to this type of algorithm is what we call the "Layerwise Separation Property" of a Planar Graph problem. Problems having this property include Planar VERTEX COVER, Planar INDEPENDENT SET, AND Planar DOMINATING SET.
Fabrizio Frati - One of the best experts on this subject based on the ideXlab platform.
-
Every Collinear Set in a Planar Graph is Free
Discrete & Computational Geometry, 2020Co-Authors: Vida Dujmović, Fabrizio Frati, Daniel Gonçalves, Pat Morin, Günter RoteAbstract:We show that if a Planar Graph G has a plane straight-line drawing in which a subset S of its vertices are collinear, then for any set of points, X , in the plane with $$|X|=|S|$$ | X | = | S | , there is a plane straight-line drawing of G in which the vertices in S are mapped to the points in X . This solves an open problem posed by Ravsky and Verbitsky (in: Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science, arXiv:0806.0253 ). In their terminology, we show that every collinear set is free. This result has applications in Graph drawing, including untangling, column Planarity, universal point subsets, and partial simultaneous drawings.
-
extending upward Planar Graph drawings
Workshop on Algorithms and Data Structures, 2019Co-Authors: Giordano Da Lozzo, Giuseppe Battista, Fabrizio FratiAbstract:In this paper we study the computational complexity of the Upward Planarity Extension problem, which takes as input an upward Planar drawing \(\varGamma _H\) of a subGraph H of a directed Graph G and asks whether \(\varGamma _H\) can be extended to an upward Planar drawing of G.
-
extending upward Planar Graph drawings
arXiv: Data Structures and Algorithms, 2019Co-Authors: Giordano Da Lozzo, Giuseppe Battista, Fabrizio FratiAbstract:In this paper we study the computational complexity of the Upward Planarity Extension problem, which takes in input an upward Planar drawing $\Gamma_H$ of a subGraph $H$ of a directed Graph $G$ and asks whether $\Gamma_H$ can be extended to an upward Planar drawing of $G$. Our study fits into the line of research on the extensibility of partial representations, which has recently become a mainstream in Graph Drawing. We show the following results. First, we prove that the Upward Planarity Extension problem is NP-complete, even if $G$ has a prescribed upward embedding, the vertex set of $H$ coincides with the one of $G$, and $H$ contains no edge. Second, we show that the Upward Planarity Extension problem can be solved in $O(n \log n)$ time if $G$ is an $n$-vertex upward Planar $st$-Graph. This result improves upon a known $O(n^2)$-time algorithm, which however applies to all $n$-vertex single-source upward Planar Graphs. Finally, we show how to solve in polynomial time a surprisingly difficult version of the Upward Planarity Extension problem, in which $G$ is a directed path or cycle with a prescribed upward embedding, $H$ contains no edges, and no two vertices share the same $y$-coordinate in $\Gamma_H$.
-
Drawing Planar Graphs with Many Collinear Vertices
arXiv: Computational Geometry, 2016Co-Authors: Giordano Da Lozzo, Fabrizio Frati, Vida Dujmović, Tamara Mchedlidze, Vincenzo RoselliAbstract:Consider the following problem: Given a Planar Graph $G$, what is the maximum number $p$ such that $G$ has a Planar straight-line drawing with $p$ collinear vertices? This problem resides at the core of several Graph drawing problems, including universal point subsets, untangling, and column Planarity. The following results are known for it: Every $n$-vertex Planar Graph has a Planar straight-line drawing with $\Omega(\sqrt{n})$ collinear vertices; for every $n$, there is an $n$-vertex Planar Graph whose every Planar straight-line drawing has $O(n^\sigma)$ collinear vertices, where $\sigma
-
Morphing Planar Graph drawings optimally
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2014Co-Authors: Paola Angelini, Maurizio Patrignani, Giordano Da Lozzo, Fabrizio Frati, Giuseppe Battista, Vincenzo RoselliAbstract:We provide an algorithm for computing a Planar morph between any two Planar straight-line drawings of any $n$-vertex plane Graph in $O(n)$ morphing steps, thus improving upon the previously best known $O(n^2)$ upper bound. Further, we prove that our algorithm is optimal, that is, we show that there exist two Planar straight-line drawings $\Gamma_s$ and $\Gamma_t$ of an $n$-vertex plane Graph $G$ such that any Planar morph between $\Gamma_s$ and $\Gamma_t$ requires $\Omega(n)$ morphing steps.
Vincenzo Roselli - One of the best experts on this subject based on the ideXlab platform.
-
Drawing Planar Graphs with Many Collinear Vertices
arXiv: Computational Geometry, 2016Co-Authors: Giordano Da Lozzo, Fabrizio Frati, Vida Dujmović, Tamara Mchedlidze, Vincenzo RoselliAbstract:Consider the following problem: Given a Planar Graph $G$, what is the maximum number $p$ such that $G$ has a Planar straight-line drawing with $p$ collinear vertices? This problem resides at the core of several Graph drawing problems, including universal point subsets, untangling, and column Planarity. The following results are known for it: Every $n$-vertex Planar Graph has a Planar straight-line drawing with $\Omega(\sqrt{n})$ collinear vertices; for every $n$, there is an $n$-vertex Planar Graph whose every Planar straight-line drawing has $O(n^\sigma)$ collinear vertices, where $\sigma
-
Morphing Planar Graph drawings optimally
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2014Co-Authors: Paola Angelini, Maurizio Patrignani, Giordano Da Lozzo, Fabrizio Frati, Giuseppe Battista, Vincenzo RoselliAbstract:We provide an algorithm for computing a Planar morph between any two Planar straight-line drawings of any $n$-vertex plane Graph in $O(n)$ morphing steps, thus improving upon the previously best known $O(n^2)$ upper bound. Further, we prove that our algorithm is optimal, that is, we show that there exist two Planar straight-line drawings $\Gamma_s$ and $\Gamma_t$ of an $n$-vertex plane Graph $G$ such that any Planar morph between $\Gamma_s$ and $\Gamma_t$ requires $\Omega(n)$ morphing steps.
-
morphing Planar Graph drawings efficiently
Graph Drawing, 2013Co-Authors: Paola Angelini, Maurizio Patrignani, Fabrizio Frati, Vincenzo RoselliAbstract:A morph between two straight-line Planar drawings of the same Graph is a continuous transformation from the first to the second drawing such that Planarity is preserved at all times. Each step of the morph moves each vertex at constant speed along a straight line. Although the existence of a morph between any two drawings was established several decades ago, only recently it has been proved that a polynomial number of steps suffices to morph any two Planar straight-line drawings. Namely, at SODA 2013, Alamdari et al. [1] proved that any two Planar straight-line drawings of a Planar Graph can be morphed in On 4 steps, while On 2 steps suffice if we restrict to maximal Planar Graphs. In this paper, we improve upon such results, by showing an algorithm to morph any two Planar straight-line drawings of a Planar Graph in On 2 steps; further, we show that a morph with On steps exists between any two Planar straight-line drawings of a series-parallel Graph.
-
morphing Planar Graph drawings with a polynomial number of steps
Symposium on Discrete Algorithms, 2013Co-Authors: Soroush Alamdari, Maurizio Patrignani, Fabrizio Frati, Vincenzo Roselli, Giuseppe Battista, Paola Angelini, Anna Lubiw, Timothy M Chan, Sahil Singla, Bryan T WilkinsonAbstract:In 1944, Cairns proved the following theorem: given any two straight-line Planar drawings of a triangulation with the same outer face, there exists a morph (i.e., a continuous transformation) between the two drawings so that the drawing remains straight-line Planar at all times. Cairns's original proof required exponentially many morphing steps. We prove that there is a morph that consists of O(n2) steps, where each step is a linear morph that moves each vertex at constant speed along a straight line. Using a known result on compatible triangulations this implies that for a general Planar Graph G and any two straight-line Planar drawings of G with the same embedding, there is a morph between the two drawings that preserves straight-line Planarity and consists of O(n4) steps.
Jochen Alber - One of the best experts on this subject based on the ideXlab platform.
-
parameterized complexity exponential speed up for Planar Graph problems
Journal of Algorithms, 2004Co-Authors: Jochen Alber, Henning Fernau, Rolf NiedermeierAbstract:We discuss general techniques, centered around the "Layerwise Separation Property" (LSP) of a Planar Graph problem, that allow to develop algorithms with running time c√k|G|, given an instance G of a problem on Planar Graphs with parameter k. Problems having LSP include Planar VERTEX COVER. Planar INDEPENDENT SET, and Planar DOMINATING SET. Extensions of our speed-up technique to basically all fixed-parameter tractable Planar Graph problems are also exhibited. Moreover, we relate, e.g., the domination number or the vertex cover number, with the treewidth of a plane Graph.
-
parameterized complexity exponential speed up for Planar Graph problems
International Colloquium on Automata Languages and Programming, 2001Co-Authors: Jochen Alber, Henning Fernau, Rolf NiedermeierAbstract:A parameterized problem is fixed parameter tractable if it admits a solving algorithm whose running time on input instance (I, k) is f(k)ċ|I|α, where f is an arbitrary function depending only on k. Typically, f is some exponential function, e.g., f(k) = ck for constant c. We describe general techniques to obtain growth of the form f(k) = ck for a large variety of Planar Graph problems. The key to this type of algorithm is what we call the "Layerwise Separation Property" of a Planar Graph problem. Problems having this property include Planar VERTEX COVER, Planar INDEPENDENT SET, AND Planar DOMINATING SET.
Amir Abboud - One of the best experts on this subject based on the ideXlab platform.
-
near optimal compression for the Planar Graph metric
Symposium on Discrete Algorithms, 2018Co-Authors: Amir Abboud, Pawel Gawrychowski, Shay Mozes, Oren WeimannAbstract:The Planar Graph Metric Compression Problem is to compactly encode the distances among k nodes in a Planar Graph of size n. Two naive solutions are to store the Graph using O(n) bits, or to explicitly store the distance matrix with O(k2 log n) bits. The only lower bounds are from the seminal work of Gavoille, Peleg, Prennes, and Raz [SODA'01], who rule out compressions into a polynomially smaller number of bits, for weighted Planar Graphs, but leave a large gap for unweighted Planar Graphs. For example, when [Equation], the upper bound is O(n) and their constructions imply an Ω(n3/4) lower bound. This gap is directly related to other major open questions in labeling schemes, dynamic algorithms, and compact routing. Our main result is a new compression of the Planar Graph metric into [Equation] bits, which is optimal up to log factors. Our data structure circumvents an Ω(k2) lower bound of Krauthgamer, Nguyen, and Zondiner [SIDMA'14] for compression using minors, and the lower bound of Gavoille et al. for compression of weighted Planar Graphs. This is an unexpected and decisive proof that weights can make Planar Graphs inherently more complex. Moreover, we design a new Subset Distance Oracle for Planar Graphs with [Equation] space, and O(n3/4) query time. Our work carries strong messages to related fields. In particular, the famous O(n1/2) vs. Ω(n1/3) gap for distance labeling schemes in Planar Graphs cannot be resolved with the current lower bound techniques. On the positive side, we introduce the powerful tool of unit-monge to Planar Graph algorithms.
-
near optimal compression for the Planar Graph metric
arXiv: Data Structures and Algorithms, 2017Co-Authors: Amir Abboud, Pawel Gawrychowski, Shay Mozes, Oren WeimannAbstract:The Planar Graph Metric Compression Problem is to compactly encode the distances among $k$ nodes in a Planar Graph of size $n$. Two na\"ive solutions are to store the Graph using $O(n)$ bits, or to explicitly store the distance matrix with $O(k^2 \log{n})$ bits. The only lower bounds are from the seminal work of Gavoille, Peleg, Prennes, and Raz [SODA'01], who rule out compressions into a polynomially smaller number of bits, for {\em weighted} Planar Graphs, but leave a large gap for unweighted Planar Graphs. For example, when $k=\sqrt{n}$, the upper bound is $O(n)$ and their constructions imply an $\Omega(n^{3/4})$ lower bound. This gap is directly related to other major open questions in labelling schemes, dynamic algorithms, and compact routing. Our main result is a new compression of the Planar Graph metric into $\tilde{O}(\min (k^2 , \sqrt{k\cdot n}))$ bits, which is optimal up to log factors. Our data structure breaks an $\Omega(k^2)$ lower bound of Krauthgamer, Nguyen, and Zondiner [SICOMP'14] for compression using minors, and the lower bound of Gavoille et al. for compression of weighted Planar Graphs. This is an unexpected and decisive proof that weights can make Planar Graphs inherently more complex. Moreover, we design a new {\em Subset Distance Oracle} for Planar Graphs with $\tilde O(\sqrt{k\cdot n})$ space, and $\tilde O(n^{3/4})$ query time. Our work carries strong messages to related fields. In particular, the famous $O(n^{1/2})$ vs. $\Omega(n^{1/3})$ gap for distance labelling schemes in Planar Graphs {\em cannot} be resolved with the current lower bound techniques.
-
popular conjectures as a barrier for dynamic Planar Graph algorithms
Foundations of Computer Science, 2016Co-Authors: Amir Abboud, Soren DahlgaardAbstract:The dynamic shortest paths problem on Planar Graphs asks us to preprocess a Planar Graph G such that we may support insertions and deletions of edges in G as well as distance queries between any two nodes u, v subject to the constraint that the Graph remains Planar at all times. This problem has been extensively studied in both the theory and experimental communities over the past decades. The best known algorithm performs queries and updates in O(n2/3) time, based on ideas of a seminal paper by Fakcharoenphol and Rao [FOCS'01]. A (1+e)-approximation algorithm of Abraham et al. [STOC'12] performs updates and queries in O(√n) time. An algorithm with a more practical O(polylog(n)) runtime would be a major breakthrough. However, such runtimes are only known for a (1+e)-approximation in a model where only restricted weight updates are allowed due to Abraham et al. [SODA'16], or for easier problems like connectivity. In this paper, we follow a recent and very active line of work on showing lower bounds for polynomial time problems based on popular conjectures, obtaining the first such results for natural problems in Planar Graphs. Such results were previously out of reach due to the highly non-Planar nature of known reductions and the impossibility of "Planarizing gadgets". We introduce a new framework which is inspired by techniques from the literatures on distance labelling schemes and on parameterized complexity. Using our framework, we show that no algorithm for dynamic shortest paths or maximum weight bipartite matching in Planar Graphs can support both updates and queries in amortized O(n1/2-e) time, for any e>0, unless the classical all-pairs-shortest-paths problem can be solved in truly subcubic time, which is widely believed to be impossible. We extend these results to obtain strong lower bounds for other related problems as well as for possible trade-offs between query and update time. Interestingly, our lower bounds hold even in very restrictive models where only weight updates are allowed.
-
popular conjectures as a barrier for dynamic Planar Graph algorithms
arXiv: Data Structures and Algorithms, 2016Co-Authors: Amir Abboud, Soren DahlgaardAbstract:The dynamic shortest paths problem on Planar Graphs asks us to preprocess a Planar Graph $G$ such that we may support insertions and deletions of edges in $G$ as well as distance queries between any two nodes $u,v$ subject to the constraint that the Graph remains Planar at all times. This problem has been extensively studied in both the theory and experimental communities over the past decades and gets solved millions of times every day by companies like Google, Microsoft, and Uber. The best known algorithm performs queries and updates in $\tilde{O}(n^{2/3})$ time, based on ideas of a seminal paper by Fakcharoenphol and Rao [FOCS'01]. A $(1+\varepsilon)$-approximation algorithm of Abraham et al. [STOC'12] performs updates and queries in $\tilde{O}(\sqrt{n})$ time. An algorithm with $O(polylog(n))$ runtime would be a major breakthrough. However, such runtimes are only known for a $(1+\varepsilon)$-approximation in a model where only restricted weight updates are allowed due to Abraham et al. [SODA'16], or for easier problems like connectivity. In this paper, we follow a recent and very active line of work on showing lower bounds for polynomial time problems based on popular conjectures, obtaining the first such results for natural problems in Planar Graphs. Such results were previously out of reach due to the highly non-Planar nature of known reductions and the impossibility of "Planarizing gadgets". We introduce a new framework which is inspired by techniques from the literatures on distance labelling schemes and on parameterized complexity. Using our framework, we show that no algorithm for dynamic shortest paths or maximum weight bipartite matching in Planar Graphs can support both updates and queries in amortized $O(n^{\frac{1}{2}-\varepsilon})$ time, for $\varepsilon>0$, unless the classical APSP problem can be solved in truly subcubic time, [...]
