2021 [ to top ]

• 
  Bläsius, Thomas; Friedrich, Tobias; Göbel, Andreas; Levy, Jordi; Rothenberger, RalfThe Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability. Symposium on Discrete Algorithms (SODA) 2021
  [ Abstract ] [ BibTeX ] [ Download ]
   
  Satisfiability is considered the canonical NP-complete problem and is used as a starting point for hardness reductions in theory, while in practice heuristic SAT solving algorithms can solve large-scale industrial SAT instances very efficiently. This disparity between theory and practice is believed to be a result of inherent properties of industrial SAT instances that make them tractable. Two characteristic properties seem to be prevalent in the majority of real-world SAT instances, heterogeneous degree distribution and locality. To understand the impact of these two properties on SAT, we study the proof complexity of random k-SAT models that allow to control heterogeneity and locality. Our findings show that heterogeneity alone does not make SAT easy as heterogeneous random k-SAT instances have superpolynomial resolution size. This implies intractability of these instances for modern SAT-solvers. On the other hand, modeling locality with an underlying geometry leads to small unsatisfiable subformulas, which can be found within polynomial time. A key ingredient for the result on geometric random k-SAT can be found in the complexity of higher-order Voronoi diagrams. As an additional technical contribution, we show an upper bound on the number of non-empty Voronoi regions, that holds for points with random positions in a very general setting. In particular, it covers arbitrary p-norms, higher dimensions, and weights affecting the area of influence of each point multiplicatively. Our bound is linear in the total weight. This is in stark contrast to quadratic lower bounds for the worst case.
  @inproceedings{blasius2021impact, abstract = {Satisfiability is considered the canonical NP-complete problem and is used as a starting point for hardness reductions in theory, while in practice heuristic SAT solving algorithms can solve large-scale industrial SAT instances very efficiently. This disparity between theory and practice is believed to be a result of inherent properties of industrial SAT instances that make them tractable. Two characteristic properties seem to be prevalent in the majority of real-world SAT instances, heterogeneous degree distribution and locality. To understand the impact of these two properties on SAT, we study the proof complexity of random k-SAT models that allow to control heterogeneity and locality. Our findings show that heterogeneity alone does not make SAT easy as heterogeneous random k-SAT instances have superpolynomial resolution size. This implies intractability of these instances for modern SAT-solvers. On the other hand, modeling locality with an underlying geometry leads to small unsatisfiable subformulas, which can be found within polynomial time. A key ingredient for the result on geometric random k-SAT can be found in the complexity of higher-order Voronoi diagrams. As an additional technical contribution, we show an upper bound on the number of non-empty Voronoi regions, that holds for points with random positions in a very general setting. In particular, it covers arbitrary p-norms, higher dimensions, and weights affecting the area of influence of each point multiplicatively. Our bound is linear in the total weight. This is in stark contrast to quadratic lower bounds for the worst case.}, author = {Bläsius, Thomas and Friedrich, Tobias and Göbel, Andreas and Levy, Jordi and Rothenberger, Ralf}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {jordilevy sat thomasblaesius andreasgoebel tobiasfriedrich ralfrothenberger soda year2021}, title = {The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability}, year = 2021 }

2020 [ to top ]

• 
  Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, AntonHyperbolic Embeddings for Near-Optimal Greedy Routing. Journal of Experimental Algorithmics (JEA) 2020
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Greedy routing computes paths between nodes in a network by successively moving to the neighbor closest to the target with respect to coordinates given by an embedding into some metric space. Its advantage is that only local information is used for routing decisions. We present different algorithms for generating graph embeddings into the hyperbolic plane that are well suited for greedy routing. In particular, our embeddings guarantee that greedy routing always succeeds in reaching the target, and we try to minimize the lengths of the resulting greedy paths. We evaluate our algorithm on multiple generated and real-world networks. For networks that are generally assumed to have a hidden underlying hyperbolic geometry, such as the Internet graph, we achieve near-optimal results (i.e., the resulting greedy paths are only slightly longer than the corresponding shortest paths). In the case of the Internet graph, they are only \(6\%\) longer when using our best algorithm, which greatly improves upon the previous best known embedding, whose creation required substantial manual intervention. In addition to measuring the stretch, we empirically evaluate our algorithms regarding the size of the coordinates of the resulting embeddings and observe how it impacts the success rate when coordinates are not represented with very high precision. Since numerical difficulties are a major issue when performing computations in the hyperbolic plane, we consider variations of our algorithm that improve the success rate when using coordinates with lower precision.
  @article{blasius2020hyperbolic, abstract = {Greedy routing computes paths between nodes in a network by successively moving to the neighbor closest to the target with respect to coordinates given by an embedding into some metric space. Its advantage is that only local information is used for routing decisions. We present different algorithms for generating graph embeddings into the hyperbolic plane that are well suited for greedy routing. In particular, our embeddings guarantee that greedy routing always succeeds in reaching the target, and we try to minimize the lengths of the resulting greedy paths. We evaluate our algorithm on multiple generated and real-world networks. For networks that are generally assumed to have a hidden underlying hyperbolic geometry, such as the Internet graph, we achieve near-optimal results (i.e., the resulting greedy paths are only slightly longer than the corresponding shortest paths). In the case of the Internet graph, they are only \(6\%\) longer when using our best algorithm, which greatly improves upon the previous best known embedding, whose creation required substantial manual intervention. In addition to measuring the stretch, we empirically evaluate our algorithms regarding the size of the coordinates of the resulting embeddings and observe how it impacts the success rate when coordinates are not represented with very high precision. Since numerical difficulties are a major issue when performing computations in the hyperbolic plane, we consider variations of our algorithm that improve the success rate when using coordinates with lower precision.}, author = {Bläsius, Thomas and Friedrich, Tobias and Katzmann, Maximilian and Krohmer, Anton}, journal = {Journal of Experimental Algorithmics (JEA)}, keywords = {jea thomasblaesius tobiasfriedrich hyperbolic_embedding antonkrohmer maximiliankatzmann year2020}, month = {March}, number = {1.3}, title = {Hyperbolic Embeddings for Near-Optimal Greedy Routing}, volume = 25, year = 2020 }
• 
  Birnick, Johann; Bläsius, Thomas; Friedrich, Tobias; Naumann, Felix; Papenbrock, Thorsten; Schirneck, MartinHitting Set Enumeration with Partial Information for Unique Column Combination Discovery. Proceedings of the VLDB Endowment 2020: 2270 - 2283
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Unique column combinations (UCCs) are a fundamental concept in relational databases. They identify entities in the data and support various data management activities. Still, UCCs are usually not explicitly defined and need to be discovered. State-of-the-art data profiling algorithms are able to efficiently discover UCCs in moderately sized datasets, but they tend to fail on large and, in particular, on wide datasets due to run time and memory limitations. In this paper, we introduce HPIValid, a novel UCC discovery algorithm that implements a faster and more resource-saving search strategy. HPIValid models the metadata discovery as a hitting set enumeration problem in hypergraphs. In this way, it combines efficient discovery techniques from data profiling research with the most recent theoretical insights into enumeration algorithms. Our evaluation shows that HPIValid is not only orders of magnitude faster than related work, it also has a much smaller memory footprint.
  @article{birnick2020hitting, abstract = {Unique column combinations (UCCs) are a fundamental concept in relational databases. They identify entities in the data and support various data management activities. Still, UCCs are usually not explicitly defined and need to be discovered. State-of-the-art data profiling algorithms are able to efficiently discover UCCs in moderately sized datasets, but they tend to fail on large and, in particular, on wide datasets due to run time and memory limitations. In this paper, we introduce HPIValid, a novel UCC discovery algorithm that implements a faster and more resource-saving search strategy. HPIValid models the metadata discovery as a hitting set enumeration problem in hypergraphs. In this way, it combines efficient discovery techniques from data profiling research with the most recent theoretical insights into enumeration algorithms. Our evaluation shows that HPIValid is not only orders of magnitude faster than related work, it also has a much smaller memory footprint.}, author = {Birnick, Johann and Bläsius, Thomas and Friedrich, Tobias and Naumann, Felix and Papenbrock, Thorsten and Schirneck, Martin}, journal = {Proceedings of the VLDB Endowment}, keywords = {pvldb thomasblaesius johannbirnick tobiasfriedrich thorstenpapenbrock felixnaumann martinschirneck year2020}, number = 11, pages = {2270 - 2283}, title = {Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery}, volume = 13, year = 2020 }
• 
  Bläsius, Thomas; Böther, Maximilian; Fischbeck, Philipp; Friedrich, Tobias; Gries, Alina; Hüffner, Falk; Kißig, Otto; Lenzner, Pascal; Molitor, Louise; Schiller, Leon; Wells, Armin; Witheger, SimonA Strategic Routing Framework and Algorithms for Computing Alternative Paths. Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) 2020: 10:1--10:14
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Traditional navigation services find the fastest route for a single driver. Though always using the fastest route seems desirable for every individual, selfish behavior can have undesirable effects such as higher energy consumption and avoidable congestion, even leading to higher overall and individual travel times. In contrast, strategic routing aims at optimizing the traffic for all agents regarding a global optimization goal. We introduce a framework to formalize real-world strategic routing scenarios as algorithmic problems and study one of them, which we call Single Alternative Path (SAP), in detail. There, we are given an original route between a single origin–destination pair. The goal is to suggest an alternative route to all agents that optimizes the overall travel time under the assumption that the agents distribute among both routes according to a psychological model, for which we introduce the concept of Pareto-conformity. We show that the SAP problem is NP-complete, even for such models. Nonetheless, assuming Pareto-conformity, we give multiple algorithms for different variants of SAP, using multi-criteria shortest path algorithms as subroutines.Moreover, we prove that several natural models are in fact Pareto-conform. The implementation and evaluation of our algorithms serve as a proof of concept, showing that SAP can be solved in reasonable time even though the algorithms have exponential running time in the worst case.
  @inproceedings{blasius2020strategic, abstract = {Traditional navigation services find the fastest route for a single driver. Though always using the fastest route seems desirable for every individual, selfish behavior can have undesirable effects such as higher energy consumption and avoidable congestion, even leading to higher overall and individual travel times. In contrast, strategic routing aims at optimizing the traffic for all agents regarding a global optimization goal. We introduce a framework to formalize real-world strategic routing scenarios as algorithmic problems and study one of them, which we call Single Alternative Path (SAP), in detail. There, we are given an original route between a single origin–destination pair. The goal is to suggest an alternative route to all agents that optimizes the overall travel time under the assumption that the agents distribute among both routes according to a psychological model, for which we introduce the concept of Pareto-conformity. We show that the SAP problem is NP-complete, even for such models. Nonetheless, assuming Pareto-conformity, we give multiple algorithms for different variants of SAP, using multi-criteria shortest path algorithms as subroutines.Moreover, we prove that several natural models are in fact Pareto-conform. The implementation and evaluation of our algorithms serve as a proof of concept, showing that SAP can be solved in reasonable time even though the algorithms have exponential running time in the worst case.}, author = {Bläsius, Thomas and Böther, Maximilian and Fischbeck, Philipp and Friedrich, Tobias and Gries, Alina and Hüffner, Falk and Kißig, Otto and Lenzner, Pascal and Molitor, Louise and Schiller, Leon and Wells, Armin and Witheger, Simon}, booktitle = {Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS)}, keywords = {maximilianboether falkhueffner tobiasfriedrich simonwietheger arminwells atmos ottokissig sys:relevantfor:ae philippfischbeck thomasblaesius louisemolitor alinagries leonschiller pascallenzner year2020}, pages = {10:1–10:14}, title = {A Strategic Routing Framework and Algorithms for Computing Alternative Paths}, volume = 85, year = 2020 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Schirneck, MartinThe Minimization of Random Hypergraphs. European Symposium on Algorithms (ESA) 2020: 21:1-21:15
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  We investigate the maximum-entropy model \(\mathcal{B}_{n,m,p}\) for random \(n\)-vertex, \(m\)-edge multi-hypergraphs with expected edge size \(pn\). We show that the expected size of the minimization \(\min(\mathcal{B}_{n,m,p})\), i.e., the number of inclusion-wise minimal edges of \(\mathcal{B}_{n,m,p}\), undergoes a phase transition with respect to \(m\). If \(m\) is at most \(1/(1-p)^(1-p)n}\), then \(\mathrm{E[|\min(\mathcal{B}_{n,m,p})|]\) is of order \(\Theta(m)\), while for \(m ge 1/(1-p)^(1-p+\varepsilon)n}\) for any \(\varepsilon > 0\), it is \(\Theta( 2^(\mathrm{H(\alpha) + (1-\alpha) \log_2 p) n/ \sqrt{n})\). Here, \(\mathrm{H}\) denotes the binary entropy function and \(alpha = - (\log_{1-p m)/n\). The result implies that the maximum expected number of minimal edges over all \(m\) is \(\Theta((1+p)^n/\sqrt{n})\). Our structural findings have algorithmic implications for minimizing an input hypergraph. This has applications in the profiling of relational databases as well as for the Orthogonal Vectors problem studied in fine-grained complexity. We make several technical contributions that are of independent interest in probability. First, we improve the Chernoff--Hoeffding theorem on the tail of the binomial distribution. In detail, we show that for a binomial variable \(Y sim \mathrm{Bin(n,p)\) and any \(0 < x < p\), it holds that \(\mathrm{P[Y le xn] = \Theta( 2^-\!\mathrm{D(x \,\|}\, p) n}/\sqrt{n})\), where \(\mathrm{D}\) is the binary Kullback--Leibler divergence between Bernoulli distributions. We give explicit upper and lower bounds on the constants hidden in the big-O notation that hold for all \(n\). Secondly, we establish the fact that the probability of a set of cardinality \(i\) being minimal after \(m\) i.i.d. maximum-entropy trials exhibits a sharp threshold behavior at \(i^* = n + \log_{1-p m\).
  @inproceedings{Blaesius20MinimizationESA, abstract = {We investigate the maximum-entropy model \(\mathcal{B}_{n,m,p}\) for random \(n\)-vertex, \(m\)-edge multi-hypergraphs with expected edge size \(pn\). We show that the expected size of the minimization \(\min(\mathcal{B}_{n,m,p})\), i.e., the number of inclusion-wise minimal edges of \(\mathcal{B}_{n,m,p}\), undergoes a phase transition with respect to \(m\). If \(m\) is at most \(1/(1-p)^{(1-p)n}\), then \(\mathrm{E}[|\min(\mathcal{B}_{n,m,p})|]\) is of order \(\Theta(m)\), while for \(m \ge 1/(1-p)^{(1-p+\varepsilon)n}\) for any \(\varepsilon > 0\), it is \(\Theta( 2^{(\mathrm{H}(\alpha) + (1-\alpha) \log_2 p) n}/ \sqrt{n})\). Here, \(\mathrm{H}\) denotes the binary entropy function and \(\alpha = - (\log_{1-p} m)/n\). The result implies that the maximum expected number of minimal edges over all \(m\) is \(\Theta((1+p)^n/\sqrt{n})\). Our structural findings have algorithmic implications for minimizing an input hypergraph. This has applications in the profiling of relational databases as well as for the Orthogonal Vectors problem studied in fine-grained complexity. We make several technical contributions that are of independent interest in probability. First, we improve the Chernoff&ndash;Hoeffding theorem on the tail of the binomial distribution. In detail, we show that for a binomial variable \(Y \sim \mathrm{Bin}(n,p)\) and any \(0 < x < p\), it holds that \(\mathrm{P}[Y \le xn] = \Theta( 2^{-\!\mathrm{D}(x \,{\|}\, p) n}/\sqrt{n})\), where \(\mathrm{D}\) is the binary Kullback&ndash;Leibler divergence between Bernoulli distributions. We give explicit upper and lower bounds on the constants hidden in the big-O notation that hold for all \(n\). Secondly, we establish the fact that the probability of a set of cardinality \(i\) being minimal after \(m\) i.i.d. maximum-entropy trials exhibits a sharp threshold behavior at \(i^* = n + \log_{1-p} m\).}, author = {Bläsius, Thomas and Friedrich, Tobias and Schirneck, Martin}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {esa thomasblaesius tobiasfriedrich martinschirneck year2020}, pages = {21:1-21:15}, title = {The Minimization of Random Hypergraphs}, year = 2020 }
• 
  Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Katzmann, MaximilianSolving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs. Symposium on the Theoretical Aspects of Computer Science (STACS) 2020: 25:1-25:14
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  The VertexCover problem is proven to be computationally hard in different ways: It is NP-complete to find an optimal solution and even NP-hard to find an approximation with reasonable factors. In contrast, recent experiments suggest that on many real-world networks the run time to solve VertexCover is way smaller than even the best known FPT-approaches can explain. Similarly, greedy algorithms deliver very good approximations to the optimal solution in practice. We link these observations to two properties that are observed in many real-world networks, namely a heterogeneous degree distribution and high clustering. To formalize these properties and explain the observed behavior, we analyze how a branch-and-reduce algorithm performs on hyperbolic random graphs, which have become increasingly popular for modeling real-world networks. In fact, we are able to show that the VertexCover problem on hyperbolic random graphs can be solved in polynomial time, with high probability. The proof relies on interesting structural properties of hyperbolic random graphs. Since these predictions of the model are interesting in their own right, we conducted experiments on real-world networks showing that these properties are also observed in practice. When utilizing the same structural properties in an adaptive greedy algorithm, further experiments suggest that, on real instances, this leads to better approximations than the standard greedy approach within reasonable time. We link these observations to two properties that are observed in many real-world networks, namely a heterogeneous degree distribution and high clustering. To formalize these properties and explain the observed behavior, we analyze how a branch-and-reduce algorithm performs on hyperbolic random graphs, which have become increasingly popular for modeling real-world networks. In fact, we are able to show that the VertexCover problem on hyperbolic random graphs can be solved in polynomial time, with high probability. The proof relies on interesting structural properties of hyperbolic random graphs. Since these predictions of the model are interesting in their own right, we conducted experiments on real-world networks showing that these properties are also observed in practice. When utilizing the same structural properties in an adaptive greedy algorithm, further experiments suggest that this leads to even better approximations than the standard greedy approach on real instances.
  @inproceedings{blasius2020solving, abstract = {The VertexCover problem is proven to be computationally hard in different ways: It is NP-complete to find an optimal solution and even NP-hard to find an approximation with reasonable factors. In contrast, recent experiments suggest that on many real-world networks the run time to solve VertexCover is way smaller than even the best known FPT-approaches can explain. Similarly, greedy algorithms deliver very good approximations to the optimal solution in practice. We link these observations to two properties that are observed in many real-world networks, namely a heterogeneous degree distribution and high clustering. To formalize these properties and explain the observed behavior, we analyze how a branch-and-reduce algorithm performs on hyperbolic random graphs, which have become increasingly popular for modeling real-world networks. In fact, we are able to show that the VertexCover problem on hyperbolic random graphs can be solved in polynomial time, with high probability. The proof relies on interesting structural properties of hyperbolic random graphs. Since these predictions of the model are interesting in their own right, we conducted experiments on real-world networks showing that these properties are also observed in practice. When utilizing the same structural properties in an adaptive greedy algorithm, further experiments suggest that, on real instances, this leads to better approximations than the standard greedy approach within reasonable time. We link these observations to two properties that are observed in many real-world networks, namely a heterogeneous degree distribution and high clustering. To formalize these properties and explain the observed behavior, we analyze how a branch-and-reduce algorithm performs on hyperbolic random graphs, which have become increasingly popular for modeling real-world networks. In fact, we are able to show that the VertexCover problem on hyperbolic random graphs can be solved in polynomial time, with high probability. The proof relies on interesting structural properties of hyperbolic random graphs. Since these predictions of the model are interesting in their own right, we conducted experiments on real-world networks showing that these properties are also observed in practice. When utilizing the same structural properties in an adaptive greedy algorithm, further experiments suggest that this leads to even better approximations than the standard greedy approach on real instances.}, author = {Bläsius, Thomas and Fischbeck, Philipp and Friedrich, Tobias and Katzmann, Maximilian}, booktitle = {Symposium on the Theoretical Aspects of Computer Science (STACS)}, keywords = {philippfischbeck thomasblaesius stacs tobiasfriedrich maximiliankatzmann hyperbolic_analysis year2020}, pages = {25:1-25:14}, title = {Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs}, year = 2020 }

2019 [ to top ]

• 
  Bläsius, Thomas; Rademacher, Marcel; Rutter, IgnazHow to Draw a Planarization. Graph Algorithms and Applications 2019: 653-682
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  We study the problem of computing straight-line drawings of non-planar graphs with few crossings. We assume that a crossing-minimization algorithm is applied first, yielding a planarization, i.e., a planar graph with a dummy vertex for each crossing, that fixes the topology of the resulting drawing. We present and evaluate two different approaches for drawing a planarization in such a way that the edges of the input graph are as straight as possible. The first approach is based on the planarity-preserving force-directed algorithm IMPRED [Simonetto et al. Computer Graphics Forum 2011], the second approach, which we call Geometric Planarization Drawing, iteratively moves vertices to their locally optimal positions in the given initial drawing. Our evaluation shows that both approaches significantly improve the initial drawing and that our geometric approach outperforms the force-directed approach. To the best of our knowledge, this is the first paper concerned with the generation of a straight-line drawing that respects an arbitrary planarization.
  @article{blasius2019planarization, abstract = {We study the problem of computing straight-line drawings of non-planar graphs with few crossings. We assume that a crossing-minimization algorithm is applied first, yielding a planarization, i.e., a planar graph with a dummy vertex for each crossing, that fixes the topology of the resulting drawing. We present and evaluate two different approaches for drawing a planarization in such a way that the edges of the input graph are as straight as possible. The first approach is based on the planarity-preserving force-directed algorithm IMPRED [Simonetto et al. Computer Graphics Forum 2011], the second approach, which we call Geometric Planarization Drawing, iteratively moves vertices to their locally optimal positions in the given initial drawing. Our evaluation shows that both approaches significantly improve the initial drawing and that our geometric approach outperforms the force-directed approach. To the best of our knowledge, this is the first paper concerned with the generation of a straight-line drawing that respects an arbitrary planarization.}, author = {Bläsius, Thomas and Rademacher, Marcel and Rutter, Ignaz}, journal = {Graph Algorithms and Applications}, keywords = {thomasblaesius year2019 jgaa}, number = 4, pages = {653-682}, title = {How to Draw a Planarization}, volume = 23, year = 2019 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Lischeid, Julius; Meeks, Kitty; Schirneck, MartinEfficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling. Algorithm Engineering and Experiments (ALENEX) 2019: 130-143
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  We devise an enumeration method for inclusion-wise minimal hitting sets in hypergraphs. It has delay \(O(m^{k^\ast+1} \cdot n^2)\) and uses linear space. Hereby, \(n\) is the number of vertices, \(m\) the number of hyperedges, and \(k^\ast\) the rank of the transversal hypergraph. In particular, on classes of hypergraphs for which the cardinality \(k^\ast\) of the largest minimal hitting set is bounded, the delay is polynomial. The algorithm solves the extension problem for minimal hitting sets as a subroutine. We show that the extension problem is W[3]-complete when parameterised by the cardinality of the set which is to be extended. For the subroutine, we give an algorithm that is optimal under the exponential time hypothesis. Despite these lower bounds, we provide empirical evidence showing that the enumeration outperforms the theoretical worst-case guarantee on hypergraphs arising in the profiling of relational databases, namely, in the detection of unique column combinations.
  @inproceedings{blasius2019efficiently, abstract = {We devise an enumeration method for inclusion-wise minimal hitting sets in hypergraphs. It has delay \(O(m^{k^\ast+1} \cdot n^2)\) and uses linear space. Hereby, \(n\) is the number of vertices, \(m\) the number of hyperedges, and \(k^\ast\) the rank of the transversal hypergraph. In particular, on classes of hypergraphs for which the cardinality \(k^\ast\) of the largest minimal hitting set is bounded, the delay is polynomial. The algorithm solves the extension problem for minimal hitting sets as a subroutine. We show that the extension problem is W[3]-complete when parameterised by the cardinality of the set which is to be extended. For the subroutine, we give an algorithm that is optimal under the exponential time hypothesis. Despite these lower bounds, we provide empirical evidence showing that the enumeration outperforms the theoretical worst-case guarantee on hypergraphs arising in the profiling of relational databases, namely, in the detection of unique column combinations.}, author = {Bläsius, Thomas and Friedrich, Tobias and Lischeid, Julius and Meeks, Kitty and Schirneck, Martin}, booktitle = {Algorithm Engineering and Experiments (ALENEX)}, keywords = {alenex kittymeeks thomasblaesius year2019 juliuslischeid tobiasfriedrich martinschirneck}, pages = {130-143}, title = {Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling}, year = 2019 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Meyer, Ulrich; Penschuck, Manuel; Weyand, ChristopherEfficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs. European Symposium on Algorithms (ESA) 2019: 21:2-21:14

  EATCS Best Paper Award
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Hyperbolic random graphs (HRG) and geometric inhomogeneous random graphs (GIRG) are two similar generative network models that were designed to resemble complex real world networks. In particular, they have a power-law degree distribution with controllable exponent \(\beta\), and high clustering that can be controlled via the temperature \(T\). We present the first implementation of an efficient GIRG generator running in expected linear time. Besides varying temperatures, it also supports underlying geometries of higher dimensions. It is capable of generating graphs with ten million edges in under a second on commodity hardware. The algorithm can be adapted to HRGs. Our resulting implementation is the fastest sequential HRG generator, despite the fact that we support non-zero temperatures. Though non-zero temperatures are crucial for many applications, most existing generators are restricted to \(T = 0\). We also support parallelization, although this is not the focus of this paper. Moreover, we note that our generators draw from the correct probability distribution, i.e., they involve no approximation. Besides the generators themselves, we also provide an efficient algorithm to determine the non-trivial dependency between the average degree of the resulting graph and the input parameters of the GIRG model. This makes it possible to specify \(\bar{d}\) as input and obtain a graph with expected average degree \(\bar{d}\). Moreover, we investigate the differences between HRGs and GIRGs, shedding new light on the nature of the relation between the two models. Although HRGs represent, in a certain sense, a special case of the GIRG model, we find that a straight-forward inclusion does not hold in practice. However, the difference is negligible for most use cases.
  @inproceedings{blaesius2019efficiently, abstract = {Hyperbolic random graphs (HRG) and geometric inhomogeneous random graphs (GIRG) are two similar generative network models that were designed to resemble complex real world networks. In particular, they have a power-law degree distribution with controllable exponent \(\beta\), and high clustering that can be controlled via the temperature \(T\). We present the first implementation of an efficient GIRG generator running in expected linear time. Besides varying temperatures, it also supports underlying geometries of higher dimensions. It is capable of generating graphs with ten million edges in under a second on commodity hardware. The algorithm can be adapted to HRGs. Our resulting implementation is the fastest sequential HRG generator, despite the fact that we support non-zero temperatures. Though non-zero temperatures are crucial for many applications, most existing generators are restricted to \(T = 0\). We also support parallelization, although this is not the focus of this paper. Moreover, we note that our generators draw from the correct probability distribution, i.e., they involve no approximation. Besides the generators themselves, we also provide an efficient algorithm to determine the non-trivial dependency between the average degree of the resulting graph and the input parameters of the GIRG model. This makes it possible to specify \(\bar{d}\) as input and obtain a graph with expected average degree \(\bar{d}\). Moreover, we investigate the differences between HRGs and GIRGs, shedding new light on the nature of the relation between the two models. Although HRGs represent, in a certain sense, a special case of the GIRG model, we find that a straight-forward inclusion does not hold in practice. However, the difference is negligible for most use cases.}, author = {Bläsius, Thomas and Friedrich, Tobias and Katzmann, Maximilian and Meyer, Ulrich and Penschuck, Manuel and Weyand, Christopher}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {esa manuelpenschuck thomasblaesius year2019 tobiasfriedrich christopherweyand hyperbolic_generation maximiliankatzmann ulrichmeyer}, note = {EATCS Best Paper Award}, pages = {21:2-21:14}, title = {Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs}, year = 2019 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Sutton, Andrew M.On the Empirical Time Complexity of Scale-Free 3-SAT at the Phase Transition. Tools and Algorithms for the Construction and Analysis of Systems (TACAS) 2019: 117-134
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  The hardness of formulas at the solubility phase transition of random propositional satisfiability (SAT) has been intensely studied for decades both empirically and theoretically. Solvers based on stochastic local search (SLS) appear to scale very well at the critical threshold, while complete backtracking solvers exhibit exponential scaling. On industrial SAT instances, this phenomenon is inverted: backtracking solvers can tackle large industrial problems, where SLS-based solvers appear to stall. Industrial instances exhibit sharply different structure than uniform random instances. Among many other properties, they are often heterogeneous in the sense that some variables appear in many while others appear in only few clauses. We conjecture that the heterogeneity of SAT formulas alone already contributes to the trade-off in performance between SLS solvers and complete backtracking solvers. We empirically determine how the run time of SLS vs. backtracking solvers depends on the heterogeneity of the input, which is controlled by drawing variables according to a scale-free distribution. Our experiments reveal that the efficiency of complete solvers at the phase transition is strongly related to the heterogeneity of the degree distribution. We report results that suggest the depth of satisfying assignments in complete search trees is influenced by the level of heterogeneity as measured by a power-law exponent. We also find that incomplete SLS solvers, which scale well on uniform instances, are not affected by heterogeneity. The main contribution of this paper utilizes the scale-free random 3-SAT model to isolate heterogeneity as an important factor in the scaling discrepancy between complete and SLS solvers at the uniform phase transition found in previous works.
  @inproceedings{blasius2019empirical, abstract = {The hardness of formulas at the solubility phase transition of random propositional satisfiability (SAT) has been intensely studied for decades both empirically and theoretically. Solvers based on stochastic local search (SLS) appear to scale very well at the critical threshold, while complete backtracking solvers exhibit exponential scaling. On industrial SAT instances, this phenomenon is inverted: backtracking solvers can tackle large industrial problems, where SLS-based solvers appear to stall. Industrial instances exhibit sharply different structure than uniform random instances. Among many other properties, they are often heterogeneous in the sense that some variables appear in many while others appear in only few clauses. We conjecture that the heterogeneity of SAT formulas alone already contributes to the trade-off in performance between SLS solvers and complete backtracking solvers. We empirically determine how the run time of SLS vs. backtracking solvers depends on the heterogeneity of the input, which is controlled by drawing variables according to a scale-free distribution. Our experiments reveal that the efficiency of complete solvers at the phase transition is strongly related to the heterogeneity of the degree distribution. We report results that suggest the depth of satisfying assignments in complete search trees is influenced by the level of heterogeneity as measured by a power-law exponent. We also find that incomplete SLS solvers, which scale well on uniform instances, are not affected by heterogeneity. The main contribution of this paper utilizes the scale-free random 3-SAT model to isolate heterogeneity as an important factor in the scaling discrepancy between complete and SLS solvers at the uniform phase transition found in previous works.}, author = {Bläsius, Thomas and Friedrich, Tobias and Sutton, Andrew M.}, booktitle = {Tools and Algorithms for the Construction and Analysis of Systems (TACAS)}, keywords = {thomasblaesius year2019 tacas tobiasfriedrich scalefree_sat andrewmsutton}, pages = {117-134}, title = {On the Empirical Time Complexity of Scale-Free 3-SAT at the Phase Transition}, year = 2019 }
• 
  Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Schirneck, MartinUnderstanding the Effectiveness of Data Reduction in Public Transportation Networks. Workshop on Algorithms and Models for the Web Graph (WAW) 2019: 87-101
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Given a public transportation network of stations and connections, we want to find a minimum subset of stations such that each connection runs through a selected station. Although this problem is NP-hard in general, real-world instances are regularly solved almost completely by a set of simple reduction rules. To explain this behavior, we view transportation networks as hitting set instances and identify two characteristic properties, locality and heterogeneity. We then devise a randomized model to generate hitting set instances with adjustable properties. While the heterogeneity does influence the effectiveness of the reduction rules, the generated instances show that locality is the significant factor. Beyond that, we prove that the effectiveness of the reduction rules is independent of the underlying graph structure. Finally, we show that high locality is also prevalent in instances from other domains, facilitating a fast computation of minimum hitting sets.
  @inproceedings{blasius2019understanding, abstract = {Given a public transportation network of stations and connections, we want to find a minimum subset of stations such that each connection runs through a selected station. Although this problem is NP-hard in general, real-world instances are regularly solved almost completely by a set of simple reduction rules. To explain this behavior, we view transportation networks as hitting set instances and identify two characteristic properties, locality and heterogeneity. We then devise a randomized model to generate hitting set instances with adjustable properties. While the heterogeneity does influence the effectiveness of the reduction rules, the generated instances show that locality is the significant factor. Beyond that, we prove that the effectiveness of the reduction rules is independent of the underlying graph structure. Finally, we show that high locality is also prevalent in instances from other domains, facilitating a fast computation of minimum hitting sets.}, author = {Bläsius, Thomas and Fischbeck, Philipp and Friedrich, Tobias and Schirneck, Martin}, booktitle = {Workshop on Algorithms and Models for the Web Graph (WAW)}, keywords = {philippfischbeck thomasblaesius year2019 tobiasfriedrich waw martinschirneck}, pages = {87-101}, title = {Understanding the Effectiveness of Data Reduction in Public Transportation Networks}, year = 2019 }

2018 [ to top ]

• 
  Bläsius, Thomas; Karrer, Annette; Rutter, IgnazSimultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices. Algorithmica 2018: 1214-1277
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  A simultaneous embedding (with fixed edges) of two graphs \(G^1\) and \(G^2\) with common graph \(G = G^1 ∩ G^2\) is a pair of planar drawings of \(G^1\) and \(G^2\) that coincide on \(G\). It is an open question whether there is a polynomial-time algorithm that decides whether two graphs admit a simultaneous embedding (problem SEFE). In this paper, we present two results. First, a set of three linear-time preprocessing algorithms that remove certain substructures from a given SEFE instance, producing a set of equivalent Sefe instances without such substructures. The structures we can remove are (1) cutvertices of the union graph \(G^∪ = G^1 ∪ G^2\) , (2) most separating pairs of \(G^∪\), and (3) connected components of G that are biconnected but not a cycle. Second, we give an \(O(n³)\)-time algorithm solving Sefe for instances with the following restriction. Let u be a pole of a P-node \(µ\) in the SPQR-tree of a block of \(G^1\) or \(G^2\). Then at most three virtual edges of \(µ\) may contain common edges incident to u. All algorithms extend to the sunflower case, i.e., to the case of more than two graphs pairwise intersecting in the same common graph.
  @article{blsius2018simultaneous, abstract = {A simultaneous embedding (with fixed edges) of two graphs \(G^1\) and \(G^2\) with common graph \(G = G^1 ∩ G^2\) is a pair of planar drawings of \(G^1\) and \(G^2\) that coincide on \(G\). It is an open question whether there is a polynomial-time algorithm that decides whether two graphs admit a simultaneous embedding (problem SEFE). In this paper, we present two results. First, a set of three linear-time preprocessing algorithms that remove certain substructures from a given SEFE instance, producing a set of equivalent Sefe instances without such substructures. The structures we can remove are (1) cutvertices of the union graph \(G^∪ = G^1 ∪ G^2\) , (2) most separating pairs of \(G^∪\), and (3) connected components of G that are biconnected but not a cycle. Second, we give an \(O(n³)\)-time algorithm solving Sefe for instances with the following restriction. Let u be a pole of a P-node \(µ\) in the SPQR-tree of a block of \(G^1\) or \(G^2\). Then at most three virtual edges of \(µ\) may contain common edges incident to u. All algorithms extend to the sunflower case, i.e., to the case of more than two graphs pairwise intersecting in the same common graph.}, author = {Bläsius, Thomas and Karrer, Annette and Rutter, Ignaz}, journal = {Algorithmica}, keywords = {algorithmica thomasblaesius year2018}, number = 4, pages = {1214-1277}, title = {Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices}, volume = 80, year = 2018 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Krohmer, AntonCliques in Hyperbolic Random Graphs. Algorithmica 2018: 2324-2344
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Most complex real world networks display scale-free features. This characteristic motivated the study of numerous random graph models with a power-law degree distribution. There is, however, no established and simple model which also has a high clustering of vertices as typically observed in real data. Hyperbolic random graphs bridge this gap. This natural model has recently been introduced by Krioukov et al. and has shown theoretically and empirically to fulfill all typical properties of real world networks, including power-law degree distribution and high clustering. We study cliques in hyperbolic random graphs \(G\) and present new results on the expected number of \(k\)-cliques \(E[K_k]\) and the size of the largest clique \(\omega(G)\). We observe that there is a phase transition at power-law exponent \(\beta = 3\). More precisely, for \(\beta\)\(\in\)\((2,3)\) we prove \(E[K_k] = \) \(n^{k(3-\beta)/2} \Theta(k)^{-k}\) and \(\omega(G) = \) \(\Theta\)\((n^{(3-\beta)/2})\), while for \(\beta \geq 3\) we prove \(E[K_k]=n \Theta(k)^{-k}\) and \(\omega(G)=\Theta(\log(n)/ \log\log n)\). Furthermore, we show that for \(\beta \geq 3\), cliques in hyperbolic random graphs can be computed in time \(O(n)\). If the underlying geometry is known, cliques can be found with worst-case runtime \(O(m n^{2.5})\) for all values of \(\beta\).
  @article{journals/algorithmica/Blasius0K18, abstract = {Most complex real world networks display scale-free features. This characteristic motivated the study of numerous random graph models with a power-law degree distribution. There is, however, no established and simple model which also has a high clustering of vertices as typically observed in real data. Hyperbolic random graphs bridge this gap. This natural model has recently been introduced by Krioukov et al. and has shown theoretically and empirically to fulfill all typical properties of real world networks, including power-law degree distribution and high clustering. We study cliques in hyperbolic random graphs \(G\) and present new results on the expected number of \(k\)-cliques \(E[K_k]\) and the size of the largest clique \(\omega(G)\). We observe that there is a phase transition at power-law exponent \(\beta = 3\). More precisely, for \(\beta\)\(\in\)\((2,3)\) we prove \(E[K_k] = \) \(n^{k(3-\beta)/2} \Theta(k)^{-k}\) and \(\omega(G) = \) \(\Theta\)\((n^{(3-\beta)/2})\), while for \(\beta \geq 3\) we prove \(E[K_k]=n \Theta(k)^{-k}\) and \(\omega(G)=\Theta(\log(n)/ \log\log n)\). Furthermore, we show that for \(\beta \geq 3\), cliques in hyperbolic random graphs can be computed in time \(O(n)\). If the underlying geometry is known, cliques can be found with worst-case runtime \(O(m n^{2.5})\) for all values of \(\beta\).}, author = {Bläsius, Thomas and Friedrich, Tobias and Krohmer, Anton}, journal = {Algorithmica}, keywords = {algorithmica thomasblaesius year2018 tobiasfriedrich antonkrohmer hyperbolic_analysis}, pages = {2324-2344}, title = {Cliques in Hyperbolic Random Graphs}, volume = 80, year = 2018 }
• 
  Bläsius, Thomas; Stumpf, Peter; Ueckerdt, TorstenLocal and Union Boxicity. Discrete Mathematics 2018: 1307 - 1315
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  The boxicity \(box(H)\) of a graph \(H\) is the smallest integer \(d\) such that \(H\) is the intersection of \(d\) interval graphs, or equivalently, that \(H\) is the intersection graph of axis-aligned boxes in \(R^d\). These intersection representations can be interpreted as covering representations of the complement \(H^c\) of \(H\) with co-interval graphs, that is, complements of interval graphs. We follow the recent framework of global, local and folded covering numbers (Knauer and Ueckerdt, 2016) to define two new parameters: the local boxicity \(box_l(H)\) and the union boxicity \(box_u(H)\) of \(H\). The union boxicity of \(H\) is the smallest \(d\) such that \(H^c\) can be covered with \(d\) vertex-disjoint unions of co-interval graphs, while the local boxicity of \(H\) is the smallest \(d\) such that \(H^c\) can be covered with co-interval graphs, at most \(d\) at every vertex. We show that for every graph \(H\) we have \(box_l(H) leq box_u(H) leq box(H) \) and that each of these inequalities can be arbitrarily far apart. Moreover, we show that local and union boxicity are also characterized by intersection representations of appropriate axis-aligned boxes in \(R^d\) . We demonstrate with a few striking examples, that in a sense, the local boxicity is a better indication for the complexity of a graph, than the classical boxicity.
  @article{blsius2018local, abstract = {The boxicity \(box(H)\) of a graph \(H\) is the smallest integer \(d\) such that \(H\) is the intersection of \(d\) interval graphs, or equivalently, that \(H\) is the intersection graph of axis-aligned boxes in \(R^d\). These intersection representations can be interpreted as covering representations of the complement \(H^c\) of \(H\) with co-interval graphs, that is, complements of interval graphs. We follow the recent framework of global, local and folded covering numbers (Knauer and Ueckerdt, 2016) to define two new parameters: the local boxicity \(box_l(H)\) and the union boxicity \(box_u(H)\) of \(H\). The union boxicity of \(H\) is the smallest \(d\) such that \(H^c\) can be covered with \(d\) vertex-disjoint unions of co-interval graphs, while the local boxicity of \(H\) is the smallest \(d\) such that \(H^c\) can be covered with co-interval graphs, at most \(d\) at every vertex. We show that for every graph \(H\) we have \(box_l(H) \leq box_u(H) \leq box(H) \) and that each of these inequalities can be arbitrarily far apart. Moreover, we show that local and union boxicity are also characterized by intersection representations of appropriate axis-aligned boxes in \(R^d\) . We demonstrate with a few striking examples, that in a sense, the local boxicity is a better indication for the complexity of a graph, than the classical boxicity.}, author = {Bläsius, Thomas and Stumpf, Peter and Ueckerdt, Torsten}, journal = {Discrete Mathematics}, keywords = {thomasblaesius year2018}, number = 5, pages = {1307 - 1315}, title = {Local and Union Boxicity}, volume = 341, year = 2018 }
• 
  Baum, Moritz; Bläsius, Thomas; Gemsa, Andreas; Rutter, Ignaz; Wegner, FranziskaScalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths. Journal of Computational Geometry 2018: 27-73
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Isocontours in road networks represent the area that is reachable from a source within a given resource limit. We study the problem of computing accurate isocontours in realistic, large-scale networks. We propose isocontours represented by polygons with minimum number of segments that separate reachable and unreachable components of the network. Since the resulting problem is not known to be solvable in polynomial time, we introduce several heuristics that run in (almost) linear time and are simple enough to be implemented in practice. A key ingredient is a new practical linear-time algorithm for minimum-link paths in simple polygons. Experiments in a challenging realistic setting show excellent performance of our algorithms in practice, computing near-optimal solutions in a few milliseconds on average, even for long ranges.
  @article{baum2018scalable, abstract = {Isocontours in road networks represent the area that is reachable from a source within a given resource limit. We study the problem of computing accurate isocontours in realistic, large-scale networks. We propose isocontours represented by polygons with minimum number of segments that separate reachable and unreachable components of the network. Since the resulting problem is not known to be solvable in polynomial time, we introduce several heuristics that run in (almost) linear time and are simple enough to be implemented in practice. A key ingredient is a new practical linear-time algorithm for minimum-link paths in simple polygons. Experiments in a challenging realistic setting show excellent performance of our algorithms in practice, computing near-optimal solutions in a few milliseconds on average, even for long ranges.}, author = {Baum, Moritz and Bläsius, Thomas and Gemsa, Andreas and Rutter, Ignaz and Wegner, Franziska}, journal = {Journal of Computational Geometry}, keywords = {thomasblaesius year2018 jocg}, number = 1, pages = {27-73}, title = {Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths}, volume = 9, year = 2018 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton; Laue, SörenEfficient Embedding of Scale-Free Graphs in the Hyperbolic Plane. Transactions on Networking 2018: 920-933
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Hyperbolic geometry appears to be intrinsic in many large real networks. We construct and implement a new maximum likelihood estimation algorithm that embeds scale-free graphs in the hyperbolic space. All previous approaches of similar embedding algorithms require at least a quadratic runtime. Our algorithm achieves quasilinear runtime, which makes it the first algorithm that can embed networks with hundreds of thousands of nodes in less than one hour. We demonstrate the performance of our algorithm on artificial and real networks. In all typical metrics, like Log-likelihood and greedy routing, our algorithm discovers embeddings that are very close to the ground truth.
  @article{journals/ton/BlasiusFKL18, abstract = {Hyperbolic geometry appears to be intrinsic in many large real networks. We construct and implement a new maximum likelihood estimation algorithm that embeds scale-free graphs in the hyperbolic space. All previous approaches of similar embedding algorithms require at least a quadratic runtime. Our algorithm achieves quasilinear runtime, which makes it the first algorithm that can embed networks with hundreds of thousands of nodes in less than one hour. We demonstrate the performance of our algorithm on artificial and real networks. In all typical metrics, like Log-likelihood and greedy routing, our algorithm discovers embeddings that are very close to the ground truth.}, author = {Bläsius, Thomas and Friedrich, Tobias and Krohmer, Anton and Laue, Sören}, journal = {Transactions on Networking}, keywords = {transnetw thomasblaesius year2018 tobiasfriedrich hyperbolic_embedding antonkrohmer}, number = {1-57570FN}, pages = {920-933}, publisher = {IEEE & ACM}, title = {Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane}, volume = 26, year = 2018 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, AntonHyperbolic Embeddings for Near-Optimal Greedy Routing. Algorithm Engineering and Experiments (ALENEX) 2018: 199-208
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Greedy routing computes paths between nodes in a network by successively moving to the neighbor closest to the target with respect to coordinates given by an embedding into some metric space. Its advantage is that only local information is used for routing decisions. We present different algorithms for generating graph embeddings into the hyperbolic plane that are well suited for greedy routing. In particular our embeddings guarantee that greedy routing always succeeds in reaching the target and we try to minimize the lengths of the resulting greedy paths. We evaluate our algorithm on multiple generated and real wold networks. For networks that are generally assumed to have a hidden underlying hyperbolic geometry, such as the Internet graph, we achieve near-optimal results, i.e., the resulting greedy paths are only slightly longer than the corresponding shortest paths. In the case of the Internet graph, they are only \(6\%\) longer when using our best algorithm, which greatly improves upon the previous best known embedding, whose creation required substantial manual intervention.
  @inproceedings{btkk2018hyperbolic, abstract = {Greedy routing computes paths between nodes in a network by successively moving to the neighbor closest to the target with respect to coordinates given by an embedding into some metric space. Its advantage is that only local information is used for routing decisions. We present different algorithms for generating graph embeddings into the hyperbolic plane that are well suited for greedy routing. In particular our embeddings guarantee that greedy routing always succeeds in reaching the target and we try to minimize the lengths of the resulting greedy paths. We evaluate our algorithm on multiple generated and real wold networks. For networks that are generally assumed to have a hidden underlying hyperbolic geometry, such as the Internet graph, we achieve near-optimal results, i.e., the resulting greedy paths are only slightly longer than the corresponding shortest paths. In the case of the Internet graph, they are only \(6\%\) longer when using our best algorithm, which greatly improves upon the previous best known embedding, whose creation required substantial manual intervention.}, author = {Bläsius, Thomas and Friedrich, Tobias and Katzmann, Maximilian and Krohmer, Anton}, booktitle = {Algorithm Engineering and Experiments (ALENEX)}, keywords = {alenex thomasblaesius year2018 tobiasfriedrich hyperbolic_embedding antonkrohmer maximiliankatzmann}, pages = {199-208}, title = {Hyperbolic Embeddings for Near-Optimal Greedy Routing}, year = 2018 }
• 
  Bläsius, Thomas; Freiberger, Cedric; Friedrich, Tobias; Katzmann, Maximilian; Montenegro-Retana, Felix; Thieffry, MarianneEfficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry. International Colloquium on Automata, Languages, and Programming (ICALP) 2018: 20:1-20:14
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  A common way to accelerate shortest path algorithms on graphs is the use of a bidirectional search, which simultaneously explores the graph from the start and the destination. It has been observed recently that this strategy performs particularly well on scale-free real-world networks. Such networks typically have a heterogeneous degree distribution (e.g., a power-law distribution) and high clustering (i.e., vertices with a common neighbor are likely to be connected themselves). These two properties can be obtained by assuming an underlying hyperbolic geometry. To explain the observed behavior of the bidirectional search, we analyze its running time on hyperbolic random graphs and prove that it is \(\tilde{O}(n\)\(^{2 - 1/ \alpha}+\)\(n^{1/(2\alpha)}\)\(+ \delta_{\max})\) with high probability, where \(\alpha\)\(\in\)\((0.5, 1)\) controls the power-law exponent of the degree distribution, and \(\delta_{\max}\) is the maximum degree. This bound is sublinear, improving the obvious worst-case linear bound. Although our analysis depends on the underlying geometry, the algorithm itself is oblivious to it.
  @inproceedings{blasius2018efficient, abstract = {A common way to accelerate shortest path algorithms on graphs is the use of a bidirectional search, which simultaneously explores the graph from the start and the destination. It has been observed recently that this strategy performs particularly well on scale-free real-world networks. Such networks typically have a heterogeneous degree distribution (e.g., a power-law distribution) and high clustering (i.e., vertices with a common neighbor are likely to be connected themselves). These two properties can be obtained by assuming an underlying hyperbolic geometry. To explain the observed behavior of the bidirectional search, we analyze its running time on hyperbolic random graphs and prove that it is \(\tilde{O}(n\)\(^{2 - 1/ \alpha}+\)\(n^{1/(2\alpha)}\)\(+ \delta_{\max})\) with high probability, where \(\alpha\)\(\in\)\((0.5, 1)\) controls the power-law exponent of the degree distribution, and \(\delta_{\max}\) is the maximum degree. This bound is sublinear, improving the obvious worst-case linear bound. Although our analysis depends on the underlying geometry, the algorithm itself is oblivious to it.}, author = {Bläsius, Thomas and Freiberger, Cedric and Friedrich, Tobias and Katzmann, Maximilian and Montenegro-Retana, Felix and Thieffry, Marianne}, booktitle = {International Colloquium on Automata, Languages, and Programming (ICALP)}, keywords = {thomasblaesius year2018 tobiasfriedrich mariannethieffry cedricfreiberger icalp maximiliankatzmann hyperbolic_analysis felixmontenegroretana}, pages = {20:1-20:14}, title = {Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry}, volume = 107, year = 2018 }
• 
  Bläsius, Thomas; Eube, Jan; Feldtkeller, Thomas; Friedrich, Tobias; Krejca, Martin S.; Lagodzinski, J. A. Gregor; Rothenberger, Ralf; Severin, Julius; Sommer, Fabian; Trautmann, JustinMemory-restricted Routing With Tiled Map Data. Systems, Man, and Cybernetics (SMC) 2018: 3347-3354
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Modern routing algorithms reduce query time by depending heavily on preprocessed data. The recently developed Navigation Data Standard (NDS) enforces a separation between algorithms and map data, rendering preprocessing inapplicable. Furthermore, map data is partitioned into tiles with respect to their geographic coordinates. With the limited memory found in portable devices, the number of tiles loaded becomes the major factor for run time. We study routing under these restrictions and present new algorithms as well as empirical evaluations. Our results show that, on average, the most efficient algorithm presented uses more than 20 times fewer tile loads than a normal A*.
  @inproceedings{blasius2018memory, abstract = {Modern routing algorithms reduce query time by depending heavily on preprocessed data. The recently developed Navigation Data Standard (NDS) enforces a separation between algorithms and map data, rendering preprocessing inapplicable. Furthermore, map data is partitioned into tiles with respect to their geographic coordinates. With the limited memory found in portable devices, the number of tiles loaded becomes the major factor for run time. We study routing under these restrictions and present new algorithms as well as empirical evaluations. Our results show that, on average, the most efficient algorithm presented uses more than 20 times fewer tile loads than a normal A*.}, author = {Bläsius, Thomas and Eube, Jan and Feldtkeller, Thomas and Friedrich, Tobias and Krejca, Martin S. and Lagodzinski, J. A. Gregor and Rothenberger, Ralf and Severin, Julius and Sommer, Fabian and Trautmann, Justin}, booktitle = {Systems, Man, and Cybernetics (SMC)}, keywords = {gregorlagodzinski janeube juliusseverin thomasblaesius martinskrejca year2018 thomasfeldtkeller smc tobiasfriedrich justintrautmann fabiansommer ralfrothenberger}, month = 10, pages = {3347-3354}, title = {Memory-restricted Routing With Tiled Map Data}, year = 2018 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, Anton; Striebel, JonathanTowards a Systematic Evaluation of Generative Network Models. Workshop on Algorithms and Models for the Web Graph (WAW) 2018: 99-114
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Generative graph models play an important role in network science. Unlike real-world networks, they are accessible for mathematical analysis and the number of available networks is not limited. The explanatory power of results on generative models, however, heavily depends on how realistic they are. We present a framework that allows for a systematic evaluation of generative network models. It is based on the question whether real-world networks can be distinguished from generated graphs with respect to certain graph parameters. As a proof of concept, we apply our framework to four popular random graph models (Erdős-Rényi, Barabási-Albert, Chung-Lu, and hyperbolic random graphs). Our experiments for example show that all four models are bad representations for Facebook's social networks, while Chung-Lu and hyperbolic random graphs are good representations for other networks, with different strengths and weaknesses.
  @inproceedings{blasius2018towards, abstract = {Generative graph models play an important role in network science. Unlike real-world networks, they are accessible for mathematical analysis and the number of available networks is not limited. The explanatory power of results on generative models, however, heavily depends on how realistic they are. We present a framework that allows for a systematic evaluation of generative network models. It is based on the question whether real-world networks can be distinguished from generated graphs with respect to certain graph parameters. As a proof of concept, we apply our framework to four popular random graph models (Erdős-Rényi, Barabási-Albert, Chung-Lu, and hyperbolic random graphs). Our experiments for example show that all four models are bad representations for Facebook's social networks, while Chung-Lu and hyperbolic random graphs are good representations for other networks, with different strengths and weaknesses.}, author = {Bläsius, Thomas and Friedrich, Tobias and Katzmann, Maximilian and Krohmer, Anton and Striebel, Jonathan}, booktitle = {Workshop on Algorithms and Models for the Web Graph (WAW)}, keywords = {jonathanstriebel thomasblaesius year2018 tobiasfriedrich antonkrohmer maximiliankatzmann waw}, pages = {99-114}, title = {Towards a Systematic Evaluation of Generative Network Models}, year = 2018 }

2017 [ to top ]

• 
  Kovacs, Robert; Seufert, Anna; Wall, Ludwig; Chen, Hsiang-Ting; Meinel, Florian; Müller, Willi; You, Sijing; Brehm, Maximilian; Striebel, Jonathan; Kommana, Yannis; Popiak, Alexander; Bläsius, Thomas; Baudisch, PatrickTrussFab: Fabricating Sturdy Large-Scale Structures on Desktop 3D Printers. Human Factors in Computing Systems (CHI) 2017: 2606-2616
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  We present TrussFab, an integrated end-to-end system that allows users to fabricate large scale structures that are sturdy enough to carry human weight. TrussFab achieves the large scale by complementing 3D print with plastic bottles. It does not use these bottles as "bricks" though, but as beams that form structurally sound node-link structures, also known as trusses, allowing it to handle the forces resulting from scale and load. TrussFab embodies the required engineering knowledge, allowing non-engineers to design such structures and to validate their design using integrated structural analysis. We have used TrussFab to design and fabricate tables and chairs, a 2.5 m long bridge strong enough to carry a human, a functional boat that seats two, and a 5 m diameter dome.
  @inproceedings{DBLP:conf/chi/KovacsSWCMMYBSK17, abstract = {We present TrussFab, an integrated end-to-end system that allows users to fabricate large scale structures that are sturdy enough to carry human weight. TrussFab achieves the large scale by complementing 3D print with plastic bottles. It does not use these bottles as "bricks" though, but as beams that form structurally sound node-link structures, also known as trusses, allowing it to handle the forces resulting from scale and load. TrussFab embodies the required engineering knowledge, allowing non-engineers to design such structures and to validate their design using integrated structural analysis. We have used TrussFab to design and fabricate tables and chairs, a 2.5 m long bridge strong enough to carry a human, a functional boat that seats two, and a 5 m diameter dome.}, author = {Kovacs, Robert and Seufert, Anna and Wall, Ludwig and Chen, Hsiang-Ting and Meinel, Florian and Müller, Willi and You, Sijing and Brehm, Maximilian and Striebel, Jonathan and Kommana, Yannis and Popiak, Alexander and Bläsius, Thomas and Baudisch, Patrick}, booktitle = {Human Factors in Computing Systems (CHI)}, keywords = {chi thomasblaesius year2017}, pages = {2606-2616}, title = {TrussFab: Fabricating Sturdy Large-Scale Structures on Desktop 3D Printers}, year = 2017 }
• 
  Bläsius, Thomas; Radermacher, Marcel; Rutter, IgnazHow to Draw a Planarization. Current Trends in Theory and Practice of Computer Science (SOFSEM) 2017: 295-308
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  We study the problem of computing straight-line drawings of non-planar graphs with few crossings. We assume that a crossingminimization algorithm is applied first, yielding a planarization, i.e., a planar graph with a dummy vertex for each crossing, that fixes the topology of the resulting drawing. We present and evaluate two different approaches for drawing a planarization in such a way that the edges of the input graph are as straight as possible. The first approach is based on the planarity-preserving force-directed algorithm ImPrEd, the second approach, which we call Geometric Planarization Drawing, iteratively moves vertices to their locally optimal positions in the given initial drawing.
  @inproceedings{DBLP:conf/sofsem/BlasiusRR17, abstract = {We study the problem of computing straight-line drawings of non-planar graphs with few crossings. We assume that a crossingminimization algorithm is applied first, yielding a planarization, i.e., a planar graph with a dummy vertex for each crossing, that fixes the topology of the resulting drawing. We present and evaluate two different approaches for drawing a planarization in such a way that the edges of the input graph are as straight as possible. The first approach is based on the planarity-preserving force-directed algorithm ImPrEd, the second approach, which we call Geometric Planarization Drawing, iteratively moves vertices to their locally optimal positions in the given initial drawing.}, author = {Bläsius, Thomas and Radermacher, Marcel and Rutter, Ignaz}, booktitle = {Current Trends in Theory and Practice of Computer Science (SOFSEM)}, keywords = {thomasblaesius year2017 sofsem}, pages = {295-308}, title = {How to Draw a Planarization}, year = 2017 }

2016 [ to top ]

• 
  Bläsius, Thomas; Lehmann, Sebastian; Rutter, IgnazOrthogonal Graph Drawing with Inflexible Edges. Computational Geometry 2016: 26-40
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  We consider the problem of creating plane orthogonal drawings of 4-planar graphs (planar graphs with maximum degree 4) with constraints on the number of bends per edge. More precisely, we have a flexibility function assigning to each edge \(e\) a natural number \(flex(e)\), its flexibility. The problem FlexDraw asks whether there exists an orthogonal drawing such that each edge \(e\) has at most \(flex(e)\) bends. It is known that FlexDraw is NP-hard if \(flex(e)=0\) for every edge \(e\). On the other hand, FlexDraw can be solved efficiently if \(flex(e) \ge 1\) and is trivial if \(flex(e) \ge 2\) for every edge \(e\). To close the gap between the NP-hardness for \(flex(e)=0\) and the efficient algorithm for \(flex(e) \ge 1\), we investigate the computational complexity of FlexDraw in case only few edges are inflexible (i.e., have flexibility 0). We show that for any \(\epsilon > 0\) FlexDraw is NP-complete for instances with \(O(n^\epsilon)\) inflexible edges with pairwise distance \(\Omega(n^{1-\epsilon})\) (including the case where they induce a matching). On the other hand, we give an FPT-algorithm with running time \(O(2^k cdot n cdot T_flow(n))\), where \(T_{flow(n)\) is the time necessary to compute a maximum flow in a planar flow network with multiple sources and sinks, and \(k\) is the number of inflexible edges having at least one endpoint of degree 4.
  @article{DBLP:journals/comgeo/BlasiusLR16, abstract = {We consider the problem of creating plane orthogonal drawings of 4-planar graphs (planar graphs with maximum degree 4) with constraints on the number of bends per edge. More precisely, we have a flexibility function assigning to each edge \(e\) a natural number \(flex(e)\), its flexibility. The problem FlexDraw asks whether there exists an orthogonal drawing such that each edge \(e\) has at most \(flex(e)\) bends. It is known that FlexDraw is NP-hard if \(flex(e)=0\) for every edge \(e\). On the other hand, FlexDraw can be solved efficiently if \(flex(e) \ge 1\) and is trivial if \(flex(e) \ge 2\) for every edge \(e\). To close the gap between the NP-hardness for \(flex(e)=0\) and the efficient algorithm for \(flex(e) \ge 1\), we investigate the computational complexity of FlexDraw in case only few edges are inflexible (i.e., have flexibility 0). We show that for any \(\epsilon > 0\) FlexDraw is NP-complete for instances with \(O(n^\epsilon)\) inflexible edges with pairwise distance \(\Omega(n^{1-\epsilon})\) (including the case where they induce a matching). On the other hand, we give an FPT-algorithm with running time \(O(2^k \cdot n \cdot T_{flow}(n))\), where \(T_{flow}(n)\) is the time necessary to compute a maximum flow in a planar flow network with multiple sources and sinks, and \(k\) is the number of inflexible edges having at least one endpoint of degree 4.}, author = {Bläsius, Thomas and Lehmann, Sebastian and Rutter, Ignaz}, journal = {Computational Geometry}, keywords = {CG thomasblaesius year2016}, pages = {26-40}, title = {Orthogonal Graph Drawing with Inflexible Edges}, volume = 55, year = 2016 }
• 
  Bläsius, Thomas; Rutter, IgnazA new perspective on clustered planarity as a combinatorial embedding problem. Theoretical Computer Science 2016: 306-315
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  The clustered planarity problem (c-planarity) asks whether a hierarchically clustered graph admits a planar drawing such that the clusters can be nicely represented by regions. We introduce the cd-tree data structure and give a new characterization of c-planarity. It leads to efficient algorithms for c-planarity testing in the following cases. (i) Every cluster and every co-cluster (complement of a cluster) has at most two connected components. (ii) Every cluster has at most five outgoing edges. Moreover, the cd-tree reveals interesting connections between c-planarity and planarity with constraints on the order of edges around vertices. On one hand, this gives rise to a bunch of new open problems related to c-planarity, on the other hand it provides a new perspective on previous results.
  @article{DBLP:journals/tcs/BlasiusR16, abstract = {The clustered planarity problem (c-planarity) asks whether a hierarchically clustered graph admits a planar drawing such that the clusters can be nicely represented by regions. We introduce the cd-tree data structure and give a new characterization of c-planarity. It leads to efficient algorithms for c-planarity testing in the following cases. (i) Every cluster and every co-cluster (complement of a cluster) has at most two connected components. (ii) Every cluster has at most five outgoing edges. Moreover, the cd-tree reveals interesting connections between c-planarity and planarity with constraints on the order of edges around vertices. On one hand, this gives rise to a bunch of new open problems related to c-planarity, on the other hand it provides a new perspective on previous results.}, author = {Bläsius, Thomas and Rutter, Ignaz}, journal = {Theoretical Computer Science}, keywords = {imported tcs thomasblaesius year2016 thomas}, pages = {306-315}, title = {A new perspective on clustered planarity as a combinatorial embedding problem}, volume = 609, year = 2016 }
• 
  Bläsius, Thomas; Rutter, IgnazSimultaneous PQ-Ordering with Applications to Constrained Embedding Problems. Transactions on Algorithms 2016: 16
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  In this article, we define and study the new problem of SIMULTANEOUS PQ-ORDERING. Its input consists of a set of PQ-trees, which represent sets of circular orders of their leaves, together with a set of child-parent relations between these PQ-trees, such that the leaves of the child form a subset of the leaves of the parent. SIMULTANEOUS PQ-ORDERING asks whether orders of the leaves of each of the trees can be chosen simultaneously; that is, for every child-parent relation, the order chosen for the parent is an extension of the order chosen for the child. We show that SIMULTANEOUS PQ-ORDERING is NP-complete in general, and we identify a family of instances that can be solved efficiently, the 2-fixed instances. We show that this result serves as a framework for several other problems that can be formulated as instances of SIMULTANEOUS PQ-ORDERING. In particular, we give linear-time algorithms for recognizing simultaneous interval graphs and extending partial interval representations. Moreover, we obtain a linear-time algorithm for PARTIALLY PQ-CONSTRAINED PLANARITY for biconnected graphs, which asks for a planar embedding in the presence of 16 PQ-trees that restrict the possible orderings of edges around vertices, and a quadratic-time algorithm for SIMULTANEOUS EMBEDDING WITH FIXED EDGES for biconnected graphs with a connected intersection. Both results can be extended to the case where the input graphs are not necessarily biconnected but have the property that each cutvertex is contained in at most two nontrivial blocks. This includes, for example, the case where both graphs have a maximum degree of 5.
  @article{DBLP:journals/talg/BlasiusR16, abstract = {In this article, we define and study the new problem of SIMULTANEOUS PQ-ORDERING. Its input consists of a set of PQ-trees, which represent sets of circular orders of their leaves, together with a set of child-parent relations between these PQ-trees, such that the leaves of the child form a subset of the leaves of the parent. SIMULTANEOUS PQ-ORDERING asks whether orders of the leaves of each of the trees can be chosen simultaneously; that is, for every child-parent relation, the order chosen for the parent is an extension of the order chosen for the child. We show that SIMULTANEOUS PQ-ORDERING is NP-complete in general, and we identify a family of instances that can be solved efficiently, the 2-fixed instances. We show that this result serves as a framework for several other problems that can be formulated as instances of SIMULTANEOUS PQ-ORDERING. In particular, we give linear-time algorithms for recognizing simultaneous interval graphs and extending partial interval representations. Moreover, we obtain a linear-time algorithm for PARTIALLY PQ-CONSTRAINED PLANARITY for biconnected graphs, which asks for a planar embedding in the presence of 16 PQ-trees that restrict the possible orderings of edges around vertices, and a quadratic-time algorithm for SIMULTANEOUS EMBEDDING WITH FIXED EDGES for biconnected graphs with a connected intersection. Both results can be extended to the case where the input graphs are not necessarily biconnected but have the property that each cutvertex is contained in at most two nontrivial blocks. This includes, for example, the case where both graphs have a maximum degree of 5.}, author = {Bläsius, Thomas and Rutter, Ignaz}, journal = {Transactions on Algorithms}, keywords = {imported thomasblaesius year2016 thomas}, number = 2, pages = 16, title = {Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems}, volume = 12, year = 2016 }
• 
  Bläsius, Thomas; Rutter, Ignaz; Wagner, DorotheaOptimal Orthogonal Graph Drawing with Convex Bend Costs. Transactions on Algorithms 2016: 33
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Traditionally, the quality of orthogonal planar drawings is quantified by the total number off bends or the maximum number of bends per edge. However, this neglects that, in typical applications, edges have varying importance. We consider the problem OptimalFlexDraw that is defined as follows. Given a planar graph \(G\) on \(n\) vertices with maximum degree 4 (4-planar graph) and for each edge \(e\) a cost function \(cost_e \colon N_0 \rightarrow R\) defining costs depending on the number of bends \(e\) has, compute a planar orthogonal drawing of \(G\) of minimum cost. In this generality OptimalFlexDraw is NP-hard. We show that it can be solved efficiently if (1) the cost function of each edge is convex and (2) the first bend on each edge does not cause any cost. Our algorithm takes time \(O(n, cdot, T_flow(n)\) and \(O(n^2, cdot, T_flow(n))\) for biconnected and connected graphs, respectively, where \(T_{flow(n)\) denotes the time to compute a minimum-cost flow in a planar network with multiple sources and sinks. Our result is the first polynomial-time bend-optimization algorithm for general 4-planar graphs optimizing over all embeddings. Previous work considers restricted graph classes and unit costs.
  @article{DBLP:journals/talg/BlasiusRW16, abstract = {Traditionally, the quality of orthogonal planar drawings is quantified by the total number off bends or the maximum number of bends per edge. However, this neglects that, in typical applications, edges have varying importance. We consider the problem OptimalFlexDraw that is defined as follows. Given a planar graph \(G\) on \(n\) vertices with maximum degree 4 (4-planar graph) and for each edge \(e\) a cost function \(cost_e \colon N_0 \rightarrow R\) defining costs depending on the number of bends \(e\) has, compute a planar orthogonal drawing of \(G\) of minimum cost. In this generality OptimalFlexDraw is NP-hard. We show that it can be solved efficiently if (1) the cost function of each edge is convex and (2) the first bend on each edge does not cause any cost. Our algorithm takes time \(O(n, \cdot, T_{flow}(n)\) and \(O(n^2, \cdot, T_{flow}(n))\) for biconnected and connected graphs, respectively, where \(T_{flow}(n)\) denotes the time to compute a minimum-cost flow in a planar network with multiple sources and sinks. Our result is the first polynomial-time bend-optimization algorithm for general 4-planar graphs optimizing over all embeddings. Previous work considers restricted graph classes and unit costs.}, author = {Bläsius, Thomas and Rutter, Ignaz and Wagner, Dorothea}, journal = {Transactions on Algorithms}, keywords = {talg thomasblaesius year2016}, number = 3, pages = 33, title = {Optimal Orthogonal Graph Drawing with Convex Bend Costs}, volume = 12, year = 2016 }
• 
  Baum, Moritz; Bläsius, Thomas; Gemsa, Andreas; Rutter, Ignaz; Wegner, FranziskaScalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths. European Symposium on Algorithms (ESA) 2016: 7:1-7:18
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Isocontours in road networks represent the area that is reachable from a source within a given resource limit. We study the problem of computing accurate isocontours in realistic, large-scale networks. We propose isocontours represented by polygons with minimum number of segments that separate reachable and unreachable components of the network. Since the resulting problem is not known to be solvable in polynomial time, we introduce several heuristics that run in (almost) linear time and are simple enough to be implemented in practice. A key ingredient is a new practical linear-time algorithm for minimum-link paths in simple polygons. Experiments in a challenging realistic setting show excellent performance of our algorithms in practice, computing near-optimal solutions in a few milliseconds on average, even for long ranges.
  @inproceedings{DBLP:conf/esa/BaumBGRW16, abstract = {Isocontours in road networks represent the area that is reachable from a source within a given resource limit. We study the problem of computing accurate isocontours in realistic, large-scale networks. We propose isocontours represented by polygons with minimum number of segments that separate reachable and unreachable components of the network. Since the resulting problem is not known to be solvable in polynomial time, we introduce several heuristics that run in (almost) linear time and are simple enough to be implemented in practice. A key ingredient is a new practical linear-time algorithm for minimum-link paths in simple polygons. Experiments in a challenging realistic setting show excellent performance of our algorithms in practice, computing near-optimal solutions in a few milliseconds on average, even for long ranges.}, author = {Baum, Moritz and Bläsius, Thomas and Gemsa, Andreas and Rutter, Ignaz and Wegner, Franziska}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {ESA thomasblaesius year2016}, pages = {7:1-7:18}, title = {Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths}, year = 2016 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Krohmer, AntonHyperbolic Random Graphs: Separators and Treewidth. European Symposium on Algorithms (ESA) 2016: 15:1-15:16
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  When designing and analyzing algorithms, one can obtain better and more realistic results for practical instances by assuming a certain probability distribution on the input. The worst-case run-time is then replaced by the expected run-time or by bounds that hold with high probability (whp), i.e., with probability \(1 - O(1/n)\), on the random input. Hyperbolic random graphs can be used to model complex real-world networks as they share many important properties such as a small diameter, a large clustering coefficient, and a power-law degree-distribution. Divide and conquer is an important algorithmic design principle that works particularly well if the instance admits small separators. We show that hyperbolic random graphs in fact have comparatively small separators. More precisely, we show that a hyperbolic random graph can be expected to have a balanced separator hierarchy with separators of size \(O(\sqrt{n^{(3-\beta)}})\), \(O(\log n)\), and \(O(1)\) if \(2 < \beta < 3\), \(\beta = 3\) and \(3 < \beta\), respectively (\(\beta\) is the power-law exponent). We infer that these graphs have whp a treewidth of \(O(\sqrt{n^{(3 - \beta)}})\), \(O(\log^{2}n)\), and \(O(\log n)\), respectively. For \(2 < \beta < 3\), this matches a known lower bound. For the more realistic (but harder to analyze) binomial model, we still prove a sublinear bound on the treewidth. To demonstrate the usefulness of our results, we apply them to obtain fast matching algorithms and an approximation scheme for Independent Set.
  @inproceedings{DBLP:conf/esa/BlasiusFK16, abstract = {When designing and analyzing algorithms, one can obtain better and more realistic results for practical instances by assuming a certain probability distribution on the input. The worst-case run-time is then replaced by the expected run-time or by bounds that hold with high probability (whp), i.e., with probability \(1 - O(1/n)\), on the random input. Hyperbolic random graphs can be used to model complex real-world networks as they share many important properties such as a small diameter, a large clustering coefficient, and a power-law degree-distribution. Divide and conquer is an important algorithmic design principle that works particularly well if the instance admits small separators. We show that hyperbolic random graphs in fact have comparatively small separators. More precisely, we show that a hyperbolic random graph can be expected to have a balanced separator hierarchy with separators of size \(O(\sqrt{n^{(3-\beta)}})\), \(O(\log n)\), and \(O(1)\) if \(2 < \beta < 3\), \(\beta = 3\) and \(3 < \beta\), respectively (\(\beta\) is the power-law exponent). We infer that these graphs have whp a treewidth of \(O(\sqrt{n^{(3 - \beta)}})\), \(O(\log^{2}n)\), and \(O(\log n)\), respectively. For \(2 < \beta < 3\), this matches a known lower bound. For the more realistic (but harder to analyze) binomial model, we still prove a sublinear bound on the treewidth. To demonstrate the usefulness of our results, we apply them to obtain fast matching algorithms and an approximation scheme for Independent Set.}, author = {Bläsius, Thomas and Friedrich, Tobias and Krohmer, Anton}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {ESA thomasblaesius year2016 tobiasfriedrich antonkrohmer hyperbolic_analysis}, pages = {15:1-15:16}, title = {Hyperbolic Random Graphs: Separators and Treewidth}, year = 2016 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton; Laue, SörenEfficient Embedding of Scale-Free Graphs in the Hyperbolic Plane. European Symposium on Algorithms (ESA) 2016: 16:1-16:18

  EATCS Best Paper Award
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Hyperbolic geometry appears to be intrinsic in many large real networks. We construct and implement a new maximum likelihood estimation algorithm that embeds scale-free graphs in the hyperbolic space. All previous approaches of similar embedding algorithms require a runtime of \(\Omega(n^{2})\). Our algorithm achieves quasilinear runtime, which makes it the first algorithm that can embed networks with hundreds of thousands of nodes in less than one hour. We demonstrate the performance of our algorithm on artificial and real networks. In all typical metrics like Log-likelihood and greedy routing our algorithm discovers embeddings that are very close to the ground truth.
  @inproceedings{DBLP:conf/esa/BlasiusFKL16, abstract = {Hyperbolic geometry appears to be intrinsic in many large real networks. We construct and implement a new maximum likelihood estimation algorithm that embeds scale-free graphs in the hyperbolic space. All previous approaches of similar embedding algorithms require a runtime of \(\Omega(n^{2})\). Our algorithm achieves quasilinear runtime, which makes it the first algorithm that can embed networks with hundreds of thousands of nodes in less than one hour. We demonstrate the performance of our algorithm on artificial and real networks. In all typical metrics like Log-likelihood and greedy routing our algorithm discovers embeddings that are very close to the ground truth.}, author = {Bläsius, Thomas and Friedrich, Tobias and Krohmer, Anton and Laue, Sören}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {ESA thomasblaesius bestpaper year2016 tobiasfriedrich hyperbolic_embedding antonkrohmer}, note = {EATCS Best Paper Award}, pages = {16:1-16:18}, title = {Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane}, year = 2016 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Schirneck, MartinThe Parameterized Complexity of Dependency Detection in Relational Databases. International Symposium on Parameterized and Exact Computation (IPEC) 2016: 6:1-6:13
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  We study the parameterized complexity of classical problems that arise in the profiling of relational data. Namely, we characterize the complexity of detecting unique column combinations (candidate keys), functional dependencies, and inclusion dependencies with the solution size as parameter. While the discovery of uniques and functional dependencies, respectively, turns out to be W[2]-complete, the detection of inclusion dependencies is one of the first natural problems proven to be complete for the class W[3]. As a side effect, our reductions give insights into the complexity of enumerating all minimal unique column combinations or functional dependencies.
  @inproceedings{DBLP:conf/iwpec/Blasius0S16, abstract = {We study the parameterized complexity of classical problems that arise in the profiling of relational data. Namely, we characterize the complexity of detecting unique column combinations (candidate keys), functional dependencies, and inclusion dependencies with the solution size as parameter. While the discovery of uniques and functional dependencies, respectively, turns out to be W[2]-complete, the detection of inclusion dependencies is one of the first natural problems proven to be complete for the class W[3]. As a side effect, our reductions give insights into the complexity of enumerating all minimal unique column combinations or functional dependencies.}, address = {Dagstuhl, Germany}, annote = {Keywords: parameterized complexity, unique column combination, functional dependency, inclusion dependency, profiling relational data}, author = {Bläsius, Thomas and Friedrich, Tobias and Schirneck, Martin}, booktitle = {International Symposium on Parameterized and Exact Computation (IPEC)}, editor = {Guo, Jiong and Hermelin, Danny}, keywords = {thomasblaesius ipec year2016 tobiasfriedrich martinschirneck}, pages = {6:1-6:13}, publisher = {Schloss Dagstuhl&ndash;Leibniz-Zentrum fuer Informatik}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, title = {The Parameterized Complexity of Dependency Detection in Relational Databases}, volume = 63, year = 2016 }

2015 [ to top ]

• 
  Bläsius, Thomas; Rutter, IgnazDisconnectivity and relative positions in simultaneous embeddings. Computational Geometry 2015: 459-478
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  For two planar graphs \(G^1 = ( V^1, E^1)\) and \(G^2 = ( V^2, E^2)\) sharing a common subgraph \(G = G^1 \cap G^2\) the problem Simultaneous Embedding with Fixed Edges (SEFE) asks whether they admit planar drawings such that the common graph is drawn the same. Previous algorithms only work for cases where \(G\) is connected, and hence do not need to handle relative positions of connected components. We consider the problem where \(G\), \(G^1\) and \(G^2\) are not necessarily connected.First, we show that a general instance of SEFE can be reduced in linear time to an equivalent instance where \(V^1 = V^2\) and \(G^1\) and \(G^2\) are connected. Second, for the case where \(G\) consists of disjoint cycles, we introduce the CC-tree which represents all embeddings of \(G\) that extend to planar embeddings of \(G^1\). We show that CC-trees can be computed in linear time, and that their intersection is again a CC-tree. This yields a linear-time algorithm for SEFE if all \(k\) input graphs (possibly \(k > 2\)) pairwise share the same set of disjoint cycles. These results, including the CC-tree, extend to the case where \(G\) consists of arbitrary connected components, each with a fixed planar embedding on the sphere. Then the running time is \(O(n^2)\).
  @article{DBLP:journals/comgeo/BlasiusR15, abstract = {For two planar graphs \(G^1 = ( V^1, E^1)\) and \(G^2 = ( V^2, E^2)\) sharing a common subgraph \(G = G^1 \cap G^2\) the problem Simultaneous Embedding with Fixed Edges (SEFE) asks whether they admit planar drawings such that the common graph is drawn the same. Previous algorithms only work for cases where \(G\) is connected, and hence do not need to handle relative positions of connected components. We consider the problem where \(G\), \(G^1\) and \(G^2\) are not necessarily connected.First, we show that a general instance of SEFE can be reduced in linear time to an equivalent instance where \(V^1 = V^2\) and \(G^1\) and \(G^2\) are connected. Second, for the case where \(G\) consists of disjoint cycles, we introduce the CC-tree which represents all embeddings of \(G\) that extend to planar embeddings of \(G^1\). We show that CC-trees can be computed in linear time, and that their intersection is again a CC-tree. This yields a linear-time algorithm for SEFE if all \(k\) input graphs (possibly \(k > 2\)) pairwise share the same set of disjoint cycles. These results, including the CC-tree, extend to the case where \(G\) consists of arbitrary connected components, each with a fixed planar embedding on the sphere. Then the running time is \(O(n^2)\).}, author = {Bläsius, Thomas and Rutter, Ignaz}, journal = {Computational Geometry}, keywords = {imported thomasblaesius year2015 thomas}, number = 6, pages = {459-478}, title = {Disconnectivity and relative positions in simultaneous embeddings}, volume = 48, year = 2015 }
• 
  Bläsius, Thomas; Lehmann, Sebastian; Rutter, IgnazOrthogonal Graph Drawing with Inflexible Edges. International Conference on Algorithms and Complexity (CIAC) 2015: 61-73
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  We consider the problem of creating plane orthogonal drawings of 4-planar graphs (planar graphs with maximum degree 4) with constraints on the number of bends per edge. More precisely, we have a flexibility function assigning to each edge \(e\) a natural number \(flex(e)\), its flexibility. The problem FlexDraw asks whether there exists an orthogonal drawing such that each edge \(e\) has at most \(flex(e)\) bends. It is known that FlexDraw is NP-hard if \(flex(e)=0\) for every edge \(e\) [7]. On the other hand, FlexDraw can be solved efficiently if \(flex(e) \ge1\) [2] and is trivial if \(flex(e) \ge 2\) [1] for every edge \(e\). To close the gap between the NP-hardness for \(flex(e)=0\) and the efficient algorithm for \(flex(e) \ge 1\), we investigate the computational complexity of FlexDraw in case only few edges are inflexible (i.e., have flexibility 0). We show that for any \(\epsilon > 0\) FlexDraw is NP-complete for instances with \(O(n^\epsilon)\) inflexible edges with pairwise distance \(\Omega(n^{1-\epsilon})\) (including the case where they induce a matching). On the other hand, we give an FPT-algorithm with running time \(O(2^k cdot n cdot T_flow(n))\), where \(T_{flow(n)\) is the time necessary to compute a maximum flow in a planar flow network with multiple sources and sinks, and \(k\) is the number of inflexible edges having at least one endpoint of degree 4.
  @inproceedings{DBLP:conf/ciac/BlasiusLR15, abstract = {We consider the problem of creating plane orthogonal drawings of 4-planar graphs (planar graphs with maximum degree 4) with constraints on the number of bends per edge. More precisely, we have a flexibility function assigning to each edge \(e\) a natural number \(flex(e)\), its flexibility. The problem FlexDraw asks whether there exists an orthogonal drawing such that each edge \(e\) has at most \(flex(e)\) bends. It is known that FlexDraw is NP-hard if \(flex(e)=0\) for every edge \(e\) [7]. On the other hand, FlexDraw can be solved efficiently if \(flex(e) \ge1\) [2] and is trivial if \(flex(e) \ge 2\) [1] for every edge \(e\). To close the gap between the NP-hardness for \(flex(e)=0\) and the efficient algorithm for \(flex(e) \ge 1\), we investigate the computational complexity of FlexDraw in case only few edges are inflexible (i.e., have flexibility 0). We show that for any \(\epsilon > 0\) FlexDraw is NP-complete for instances with \(O(n^\epsilon)\) inflexible edges with pairwise distance \(\Omega(n^{1-\epsilon})\) (including the case where they induce a matching). On the other hand, we give an FPT-algorithm with running time \(O(2^k \cdot n \cdot T_{flow}(n))\), where \(T_{flow}(n)\) is the time necessary to compute a maximum flow in a planar flow network with multiple sources and sinks, and \(k\) is the number of inflexible edges having at least one endpoint of degree 4.}, author = {Bläsius, Thomas and Lehmann, Sebastian and Rutter, Ignaz}, booktitle = {International Conference on Algorithms and Complexity (CIAC)}, keywords = {imported thomasblaesius year2015 thomas}, pages = {61-73}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Orthogonal Graph Drawing with Inflexible Edges}, volume = 9079, year = 2015 }
• 
  Alam, Md. Jawaherul; Bläsius, Thomas; Rutter, Ignaz; Ueckerdt, Torsten; Wolff, AlexanderPixel and Voxel Representations of Graphs. Graph Drawing (GD) 2015: 472-486
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  We study contact representations for graphs, which we call pixel representations in 2D and voxel representations in 3D. Our representations are based on the unit square grid whose cells we call pixels in 2D and voxels in 3D. Two pixels are adjacent if they share an edge, two voxels if they share a face. We call a connected set of pixels or voxels a blob. Given a graph, we represent its vertices by disjoint blobs such that two blobs contain adjacent pixels or voxels if and only if the corresponding vertices are adjacent. We are interested in the size of a representation, which is the number of pixels or voxels it consists of. We first show that finding minimum-size representations is NP-complete. Then, we bound representation sizes needed for certain graph classes. In 2D, we show that, for \(k\)-outerplanar graphs with \(n\) vertices, \(\Theta(kn)\) pixels are always sufficient and sometimes necessary. In particular, outerplanar graphs can be represented with a linear number of pixels, whereas general planar graphs sometimes need a quadratic number. In 3D, \(\Theta(n^2)\) voxels are always sufficient and sometimes necessary for any \(n\)-vertex graph. We improve this bound to \(\Theta(n \cdot \tau)\) for graphs of treewidth \(\tau\) and to \(O((g+1)^2 n \log^2 n)\) for graphs of genus \(g\). In particular, planar graphs admit representations with \(O(n\log^2 n)\) voxels.
  @inproceedings{DBLP:conf/gd/AlamBRUW15, abstract = {We study contact representations for graphs, which we call pixel representations in 2D and voxel representations in 3D. Our representations are based on the unit square grid whose cells we call pixels in 2D and voxels in 3D. Two pixels are adjacent if they share an edge, two voxels if they share a face. We call a connected set of pixels or voxels a blob. Given a graph, we represent its vertices by disjoint blobs such that two blobs contain adjacent pixels or voxels if and only if the corresponding vertices are adjacent. We are interested in the size of a representation, which is the number of pixels or voxels it consists of. We first show that finding minimum-size representations is NP-complete. Then, we bound representation sizes needed for certain graph classes. In 2D, we show that, for \(k\)-outerplanar graphs with \(n\) vertices, \(\Theta(kn)\) pixels are always sufficient and sometimes necessary. In particular, outerplanar graphs can be represented with a linear number of pixels, whereas general planar graphs sometimes need a quadratic number. In 3D, \(\Theta(n^2)\) voxels are always sufficient and sometimes necessary for any \(n\)-vertex graph. We improve this bound to \(\Theta(n \cdot \tau)\) for graphs of treewidth \(\tau\) and to \(O((g+1)^2 n \log^2 n)\) for graphs of genus \(g\). In particular, planar graphs admit representations with \(O(n\log^2 n)\) voxels.}, author = {Alam, Md. Jawaherul and Bläsius, Thomas and Rutter, Ignaz and Ueckerdt, Torsten and Wolff, Alexander}, booktitle = {Graph Drawing (GD)}, keywords = {imported thomasblaesius year2015 thomas GD}, pages = {472-486}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Pixel and Voxel Representations of Graphs}, volume = 9411, year = 2015 }
• 
  Bläsius, ThomasNew Approaches to Classic Graph-Embedding Problems - Orthogonal Drawings & Constrained Planarity. Doctoral Dissertation, Karlsruhe Institute of Technology 2015
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Drawings of graphs are often used to represent a given data set in a human-readable way. In this thesis, we consider different classic algorithmic problems that arise when automatically generating graph drawings. More specifically, we solve some open problems in the context of orthogonal drawings and advance the current state of research on the problems clustered planarity and simultaneous planarity.
  @phdthesis{DBLP:phd/dnb/Blasius15, abstract = {Drawings of graphs are often used to represent a given data set in a human-readable way. In this thesis, we consider different classic algorithmic problems that arise when automatically generating graph drawings. More specifically, we solve some open problems in the context of orthogonal drawings and advance the current state of research on the problems clustered planarity and simultaneous planarity.}, annote = {Doctoral Dissertation, Karlsruhe Institute of Technology}, author = {Bläsius, Thomas}, keywords = {imported thomasblaesius theses year2015}, school = {Karlsruhe Institute of Technology}, title = {New Approaches to Classic Graph-Embedding Problems - Orthogonal Drawings & Constrained Planarity}, year = 2015 }

2014 [ to top ]

• 
  Bläsius, Thomas; Krug, Marcus; Rutter, Ignaz; Wagner, DorotheaOrthogonal Graph Drawing with Flexibility Constraints. Algorithmica 2014: 859-885
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Traditionally, the quality of orthogonal planar drawings is quantified by either the total number of bends, or the maximum number of bends per edge. However, this neglects that in typical applications, edges have varying importance. In this work, we investigate an approach that allows to specify the maximum number of bends for each edge individually, depending on its importance. We consider a new problem called FlexDraw that is defined as follows. Given a planar graph \(G=(V,E)\) on \(n\) vertices with maximum degree 4 and a function \(flex \colon E \rightarrow N_0\) that assigns a flexibility to each edge, does \(G\) admit a planar embedding on the grid such that each edge \(e\) has at most \(flex(e)\) bends? Note that in our setting the combinatorial embedding of \(G\) is not fixed. FlexDraw directly extends the problem \(\beta\)-embeddability asking whether \(G\) can be embedded with at most \(\beta\) bends per edge. We give an algorithm with running-time \(O(n^2)\) solving FlexDraw when the flexibility of each edge is positive. This includes 1-embeddability as a special case and thus closes the complexity gap between 0-embeddability, which is NP-hard to decide, and 2-embeddability, which is efficiently solvable since every planar graph with maximum degree 4 admits a 2-embedding except for the octahedron. In addition to the polynomial-time algorithm we show that FlexDraw is NP-hard even if the edges with flexibility 0 induce a tree or a union of disjoint stars.
  @article{DBLP:journals/algorithmica/BlasiusKRW14, abstract = {Traditionally, the quality of orthogonal planar drawings is quantified by either the total number of bends, or the maximum number of bends per edge. However, this neglects that in typical applications, edges have varying importance. In this work, we investigate an approach that allows to specify the maximum number of bends for each edge individually, depending on its importance. We consider a new problem called FlexDraw that is defined as follows. Given a planar graph \(G=(V,E)\) on \(n\) vertices with maximum degree 4 and a function \(flex \colon E \rightarrow N_0\) that assigns a flexibility to each edge, does \(G\) admit a planar embedding on the grid such that each edge \(e\) has at most \(flex(e)\) bends? Note that in our setting the combinatorial embedding of \(G\) is not fixed. FlexDraw directly extends the problem \(\beta\)-embeddability asking whether \(G\) can be embedded with at most \(\beta\) bends per edge. We give an algorithm with running-time \(O(n^2)\) solving FlexDraw when the flexibility of each edge is positive. This includes 1-embeddability as a special case and thus closes the complexity gap between 0-embeddability, which is NP-hard to decide, and 2-embeddability, which is efficiently solvable since every planar graph with maximum degree 4 admits a 2-embedding except for the octahedron. In addition to the polynomial-time algorithm we show that FlexDraw is NP-hard even if the edges with flexibility 0 induce a tree or a union of disjoint stars.}, author = {Bläsius, Thomas and Krug, Marcus and Rutter, Ignaz and Wagner, Dorothea}, journal = {Algorithmica}, keywords = {imported thomasblaesius year2014 thomas}, number = 4, pages = {859-885}, title = {Orthogonal Graph Drawing with Flexibility Constraints}, volume = 68, year = 2014 }
• 
  Angelini, Patrizio; Bläsius, Thomas; Rutter, IgnazTesting Mutual duality of Planar graphs. Computational Geometry and Applications 2014: 325-346
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  We introduce and study the problem Mutual Planar Duality, which asks for planar graphs \(G_1\) and \(G_2\) whether \(G_1\) can be embedded such that its dual is isomorphic to \(G_2\). We show NP-completeness for general graphs and give a linear-time algorithm for biconnected graphs. We consider the common dual relation ~, where \(G_1\) ~ \(G_2\) if and only they admit embeddings that result in the same dual graph. We show that ~ is an equivalence relation on the set of biconnected graphs and devise a succinct, SPQR-tree-like representation of its equivalence classes. To solve Mutual Planar Duality for biconnected graphs, we show how to do isomorphism testing for two such representations in linear time. A special case of Mutual Planar Duality is testing whether a graph is self-dual. Our algorithm can handle the case of biconnected graphs in linear time and our NP-hardness proof extends to self-duality and also to map self-duality testing (which additionally requires to preserve the embedding).
  @article{DBLP:journals/ijcga/AngeliniBR14, abstract = {We introduce and study the problem Mutual Planar Duality, which asks for planar graphs \(G_1\) and \(G_2\) whether \(G_1\) can be embedded such that its dual is isomorphic to \(G_2\). We show NP-completeness for general graphs and give a linear-time algorithm for biconnected graphs. We consider the common dual relation &nbsp;, where \(G_1\) &nbsp; \(G_2\) if and only they admit embeddings that result in the same dual graph. We show that &nbsp; is an equivalence relation on the set of biconnected graphs and devise a succinct, SPQR-tree-like representation of its equivalence classes. To solve Mutual Planar Duality for biconnected graphs, we show how to do isomorphism testing for two such representations in linear time. A special case of Mutual Planar Duality is testing whether a graph is self-dual. Our algorithm can handle the case of biconnected graphs in linear time and our NP-hardness proof extends to self-duality and also to map self-duality testing (which additionally requires to preserve the embedding).}, author = {Angelini, Patrizio and Bläsius, Thomas and Rutter, Ignaz}, journal = {Computational Geometry and Applications}, keywords = {ijcga thomasblaesius year2014}, number = 4, pages = {325-346}, title = {Testing Mutual duality of Planar graphs}, volume = 24, year = 2014 }
• 
  Bläsius, Thomas; Brückner, Guido; Rutter, IgnazComplexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky Model. European Symposium on Algorithms (ESA) 2014: 161-172
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  We show that finding orthogonal grid-embeddings of plane graphs (planar with fixed combinatorial embedding) with the minimum number of bends in the so-called Kandinsky model (which allows vertices of degree >4) is NP-complete, thus solving a long-standing open problem. On the positive side, we give an efficient algorithm for several restricted variants, such as graphs of bounded branch width and a subexponential exact algorithm for general plane graphs.
  @inproceedings{DBLP:conf/esa/BlasiusBR14, abstract = {We show that finding orthogonal grid-embeddings of plane graphs (planar with fixed combinatorial embedding) with the minimum number of bends in the so-called Kandinsky model (which allows vertices of degree >4) is NP-complete, thus solving a long-standing open problem. On the positive side, we give an efficient algorithm for several restricted variants, such as graphs of bounded branch width and a subexponential exact algorithm for general plane graphs.}, author = {Bläsius, Thomas and Brückner, Guido and Rutter, Ignaz}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {imported thomasblaesius year2014 thomas}, pages = {161-172}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky Model}, volume = 8737, year = 2014 }
• 
  Bläsius, Thomas; Rutter, IgnazA New Perspective on Clustered Planarity as a Combinatorial Embedding Problem. Graph Drawing (GD) 2014: 440-451
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  The clustered planarity problem (\(c\)-planarity) asks whether a hierarchically clustered graph admits a planar drawing such that the clusters can be nicely represented by regions. We introduce the \(cd\)-tree data structure and give a new characterization of \(c\)-planarity. It leads to efficient algorithms for \(c\)-planarity testing in the following cases. (i) Every cluster and every co-cluster has at most two connected components. (ii) Every cluster has at most five outgoing edges. Moreover, the cd-tree reveals interesting connections between \(c\)-planarity and planarity with constraints on the order of edges around vertices. On one hand, this gives rise to a bunch of new open problems related to \(c\)-planarity, on the other hand it provides a new perspective on previous results.
  @inproceedings{DBLP:conf/gd/BlasiusR14, abstract = {The clustered planarity problem (\(c\)-planarity) asks whether a hierarchically clustered graph admits a planar drawing such that the clusters can be nicely represented by regions. We introduce the \(cd\)-tree data structure and give a new characterization of \(c\)-planarity. It leads to efficient algorithms for \(c\)-planarity testing in the following cases. (i) Every cluster and every co-cluster has at most two connected components. (ii) Every cluster has at most five outgoing edges. Moreover, the cd-tree reveals interesting connections between \(c\)-planarity and planarity with constraints on the order of edges around vertices. On one hand, this gives rise to a bunch of new open problems related to \(c\)-planarity, on the other hand it provides a new perspective on previous results.}, author = {Bläsius, Thomas and Rutter, Ignaz}, booktitle = {Graph Drawing (GD)}, keywords = {imported thomasblaesius year2014 thomas GD}, pages = {440-451}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {A New Perspective on Clustered Planarity as a Combinatorial Embedding Problem}, volume = 8871, year = 2014 }

2013 [ to top ]

• 
  Bläsius, Thomas; Kobourov, Stephen G.; Rutter, IgnazSimultaneous Embedding of Planar Graphs. Handbook of Graph Drawing and Visualization 2013: 349-381
  [ Abstract ] [ BibTeX ] [ Download ]
   
  Simultaneous embedding is concerned with simultaneously representing a series of graphs sharing some or all vertices. This forms the basis for the visualization of dynamic graphs and thus is an important field of research. Recently there has been a great deal of work investigating simultaneous embedding problems both from a theoretical and a practical point of view. We survey recent work on this topic.
  @incollection{DBLP:reference/crc/BlasiusKR13, abstract = {Simultaneous embedding is concerned with simultaneously representing a series of graphs sharing some or all vertices. This forms the basis for the visualization of dynamic graphs and thus is an important field of research. Recently there has been a great deal of work investigating simultaneous embedding problems both from a theoretical and a practical point of view. We survey recent work on this topic.}, author = {Bläsius, Thomas and Kobourov, Stephen G. and Rutter, Ignaz}, booktitle = {Handbook of Graph Drawing and Visualization}, keywords = {imported thomasblaesius year2013 thomas}, pages = {349-381}, publisher = {Chapman and Hall/CRC}, title = {Simultaneous Embedding of Planar Graphs}, year = 2013 }
• 
  Bläsius, Thomas; Karrer, Annette; Rutter, IgnazSimultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices. Graph Drawing (GD) 2013: 220-231
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  A simultaneous embedding (with fixed edges) of two graphs \(G^1\) and \(G^2\) with common graph \(G = G^1 \cap G^2\) is a pair of planar drawings of \(G^1\) and \(G^2\) that coincide on \(G\). It is an open question whether there is a polynomial-time algorithm that decides whether two graphs admit a simultaneous embedding (problem Sefe). In this paper, we present two results. First, a set of three linear-time preprocessing algorithms that remove certain substructures from a given Sefe instance, producing a set of equivalent Sefe instances without such substructures. The structures we can remove are (1) cutvertices of the union graph \(G^{\cup} = G ^1 \cup G^2\) , (2) most separating pairs of \(G^{\cup}\), and (3) connected components of \(G\) that are biconnected but not a cycle. Second, we give an \(O(n^3)\)-time algorithm solving Sefe for instances with the following restriction. Let \(u\) be a pole of a \(P\)-node \(\mu\) in the SPQR-tree of a block of \(G^1\) or \(G^2\) . Then at most three virtual edges of \(\mu\) may contain common edges incident to \(u\). All algorithms extend to the sunflower case, i.e., to the case of more than three graphs pairwise intersecting in the same common graph.
  @inproceedings{DBLP:conf/gd/BlasiusKR13, abstract = {A simultaneous embedding (with fixed edges) of two graphs \(G^1\) and \(G^2\) with common graph \(G = G^1 \cap G^2\) is a pair of planar drawings of \(G^1\) and \(G^2\) that coincide on \(G\). It is an open question whether there is a polynomial-time algorithm that decides whether two graphs admit a simultaneous embedding (problem Sefe). In this paper, we present two results. First, a set of three linear-time preprocessing algorithms that remove certain substructures from a given Sefe instance, producing a set of equivalent Sefe instances without such substructures. The structures we can remove are (1) cutvertices of the union graph \(G^{\cup} = G ^1 \cup G^2\) , (2) most separating pairs of \(G^{\cup}\), and (3) connected components of \(G\) that are biconnected but not a cycle. Second, we give an \(O(n^3)\)-time algorithm solving Sefe for instances with the following restriction. Let \(u\) be a pole of a \(P\)-node \(\mu\) in the SPQR-tree of a block of \(G^1\) or \(G^2\) . Then at most three virtual edges of \(\mu\) may contain common edges incident to \(u\). All algorithms extend to the sunflower case, i.e., to the case of more than three graphs pairwise intersecting in the same common graph.}, author = {Bläsius, Thomas and Karrer, Annette and Rutter, Ignaz}, booktitle = {Graph Drawing (GD)}, keywords = {imported thomasblaesius year2013 thomas GD}, pages = {220-231}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices}, volume = 8242, year = 2013 }
• 
  Biedl, Therese C.; Bläsius, Thomas; Niedermann, Benjamin; Nöllenburg, Martin; Prutkin, Roman; Rutter, IgnazUsing ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph Drawings. Graph Drawing (GD) 2013: 460-471
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  We present a simple and versatile formulation of grid-based graph representation problems as an integer linear program (ILP) and a corresponding SAT instance. In a grid-based representation vertices and edges correspond to axis-parallel boxes on an underlying integer grid; boxes can be further constrained in their shapes and interactions by additional problem-specific constraints. We describe a general \(d\)-dimensional model for grid representation problems. This model can be used to solve a variety of NP-hard graph problems, including pathwidth, bandwidth, optimum st-orientation, area-minimal (bar-k) visibility representation, boxicity-k graphs and others. We implemented SAT-models for all of the above problems and evaluated them on the Rome graphs collection. The experiments show that our model successfully solves NP-hard problems within few minutes on small to medium-size Rome graphs.
  @inproceedings{DBLP:conf/gd/BiedlBNNPR13, abstract = {We present a simple and versatile formulation of grid-based graph representation problems as an integer linear program (ILP) and a corresponding SAT instance. In a grid-based representation vertices and edges correspond to axis-parallel boxes on an underlying integer grid; boxes can be further constrained in their shapes and interactions by additional problem-specific constraints. We describe a general \(d\)-dimensional model for grid representation problems. This model can be used to solve a variety of NP-hard graph problems, including pathwidth, bandwidth, optimum st-orientation, area-minimal (bar-k) visibility representation, boxicity-k graphs and others. We implemented SAT-models for all of the above problems and evaluated them on the Rome graphs collection. The experiments show that our model successfully solves NP-hard problems within few minutes on small to medium-size Rome graphs.}, author = {Biedl, Therese C. and Bläsius, Thomas and Niedermann, Benjamin and Nöllenburg, Martin and Prutkin, Roman and Rutter, Ignaz}, booktitle = {Graph Drawing (GD)}, keywords = {imported thomasblaesius year2013 thomas GD}, pages = {460-471}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph Drawings}, volume = 8242, year = 2013 }
• 
  Bläsius, Thomas; Rutter, Ignaz; Wagner, DorotheaOptimal Orthogonal Graph Drawing with Convex Bend Costs. International Colloquium on Automata, Languages, and Programming (ICALP) 2013: 184-195
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Traditionally, the quality of orthogonal planar drawings is quantified by the total number of bends or the maximum number of bends per edge. However, this neglects that, in typical applications, edges have varying importance. We consider the problem OptimalFlexDraw that is defined as follows. Given a planar graph \(G\) on \(n\) vertices with maximum degree 4 (4-planar graph) and for each edge \(e\) a cost function \(cost_e \colon N_0 \rightarrow R\) defining costs depending on the number of bends \(e\) has, compute a planar orthogonal drawing of \(G\) of minimum cost. In this generality OptimalFlexDraw is NP-hard. We show that it can be solved efficiently if (1) the cost function of each edge is convex and (2) the first bend on each edge does not cause any cost. Our algorithm takes time \(O(n, cdot, T_flow(n))\) and \(O(n^2, cdot, T_flow(n))\) for biconnected and connected graphs, respectively, where \(T_{flow(n)\) denotes the time to compute a minimum-cost flow in a planar network with multiple sources and sinks. Our result is the first polynomial-time bend-optimization algorithm for general 4-planar graphs optimizing over all embeddings. Previous work considers restricted graph classes and unit costs.
  @inproceedings{DBLP:conf/icalp/BlasiusRW13, abstract = {Traditionally, the quality of orthogonal planar drawings is quantified by the total number of bends or the maximum number of bends per edge. However, this neglects that, in typical applications, edges have varying importance. We consider the problem OptimalFlexDraw that is defined as follows. Given a planar graph \(G\) on \(n\) vertices with maximum degree 4 (4-planar graph) and for each edge \(e\) a cost function \(cost_e \colon N_0 \rightarrow R\) defining costs depending on the number of bends \(e\) has, compute a planar orthogonal drawing of \(G\) of minimum cost. In this generality OptimalFlexDraw is NP-hard. We show that it can be solved efficiently if (1) the cost function of each edge is convex and (2) the first bend on each edge does not cause any cost. Our algorithm takes time \(O(n, \cdot, T_{flow}(n))\) and \(O(n^2, \cdot, T_{flow}(n))\) for biconnected and connected graphs, respectively, where \(T_{flow}(n)\) denotes the time to compute a minimum-cost flow in a planar network with multiple sources and sinks. Our result is the first polynomial-time bend-optimization algorithm for general 4-planar graphs optimizing over all embeddings. Previous work considers restricted graph classes and unit costs.}, author = {Bläsius, Thomas and Rutter, Ignaz and Wagner, Dorothea}, booktitle = {International Colloquium on Automata, Languages, and Programming (ICALP)}, keywords = {imported thomasblaesius year2013 thomas}, pages = {184-195}, series = {Lecture Notes in Computer Science}, title = {Optimal Orthogonal Graph Drawing with Convex Bend Costs}, volume = 7965, year = 2013 }
• 
  Angelini, Patrizio; Bläsius, Thomas; Rutter, IgnazTesting Mutual Duality of Planar Graphs. International Symposium on Algorithms and Computation (ISAAC) 2013: 350-360
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  We introduce and study the problem Mutual Planar Duality, which asks for planar graphs \(G_1\) and \(G_2\) whether \(G_1\) can be embedded such that its dual is isomorphic to \(G_2\). We show NP-completeness for general graphs and give a linear-time algorithm for biconnected graphs. We consider the common dual relation \(\sim\), where \(G_1 \sim G_2\) if and only they admit embeddings that result in the same dual graph. We show that ~ is an equivalence relation on the set of biconnected graphs and devise a succinct, SPQR-tree-like representation of its equivalence classes. To solve Mutual Planar Duality for biconnected graphs, we show how to do isomorphism testing for two such representations in linear time. A special case of Mutual Planar Duality is testing whether a graph is self-dual. Our algorithm can handle the case of biconnected graphs in linear time and our NP-hardness proof extends to self-duality and also to map self-duality testing (which additionally requires to preserve the embedding).
  @inproceedings{DBLP:conf/isaac/AngeliniBR13, abstract = {We introduce and study the problem Mutual Planar Duality, which asks for planar graphs \(G_1\) and \(G_2\) whether \(G_1\) can be embedded such that its dual is isomorphic to \(G_2\). We show NP-completeness for general graphs and give a linear-time algorithm for biconnected graphs. We consider the common dual relation \(\sim\), where \(G_1 \sim G_2\) if and only they admit embeddings that result in the same dual graph. We show that &nbsp; is an equivalence relation on the set of biconnected graphs and devise a succinct, SPQR-tree-like representation of its equivalence classes. To solve Mutual Planar Duality for biconnected graphs, we show how to do isomorphism testing for two such representations in linear time. A special case of Mutual Planar Duality is testing whether a graph is self-dual. Our algorithm can handle the case of biconnected graphs in linear time and our NP-hardness proof extends to self-duality and also to map self-duality testing (which additionally requires to preserve the embedding).}, author = {Angelini, Patrizio and Bläsius, Thomas and Rutter, Ignaz}, booktitle = {International Symposium on Algorithms and Computation (ISAAC)}, keywords = {imported thomasblaesius year2013 thomas}, pages = {350-360}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Testing Mutual Duality of Planar Graphs}, volume = 8283, year = 2013 }
• 
  Bläsius, Thomas; Rutter, IgnazSimultaneous PQ-Ordering with Applications to Constrained Embedding Problems. Symposium on Discrete Algorithms (SODA) 2013: 1030-1043
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  In this article, we define and study the new problem of SIMULTANEOUS PQ-ORDERING. Its input consists of a set of PQ-trees, which represent sets of circular orders of their leaves, together with a set of child-parent relations between these PQ-trees, such that the leaves of the child form a subset of the leaves of the parent. SIMULTANEOUS PQ-ORDERING asks whether orders of the leaves of each of the trees can be chosen simultaneously; that is, for every child-parent relation, the order chosen for the parent is an extension of the order chosen for the child. We show that SIMULTANEOUS PQ-ORDERING is NP-complete in general, and we identify a family of instances that can be solved efficiently, the 2-fixed instances. We show that this result serves as a framework for several other problems that can be formulated as instances of SIMULTANEOUS PQ-ORDERING. In particular, we give linear-time algorithms for recognizing simultaneous interval graphs and extending partial interval representations. Moreover, we obtain a linear-time algorithm for PARTIALLY PQ-CONSTRAINED PLANARITY for biconnected graphs, which asks for a planar embedding in the presence of 16 PQ-trees that restrict the possible orderings of edges around vertices, and a quadratic-time algorithm for SIMULTANEOUS EMBEDDING WITH FIXED EDGES for biconnected graphs with a connected intersection. Both results can be extended to the case where the input graphs are not necessarily biconnected but have the property that each cutvertex is contained in at most two nontrivial blocks. This includes, for example, the case where both graphs have a maximum degree of 5.
  @inproceedings{DBLP:conf/soda/BlasiusR13, abstract = {In this article, we define and study the new problem of SIMULTANEOUS PQ-ORDERING. Its input consists of a set of PQ-trees, which represent sets of circular orders of their leaves, together with a set of child-parent relations between these PQ-trees, such that the leaves of the child form a subset of the leaves of the parent. SIMULTANEOUS PQ-ORDERING asks whether orders of the leaves of each of the trees can be chosen simultaneously; that is, for every child-parent relation, the order chosen for the parent is an extension of the order chosen for the child. We show that SIMULTANEOUS PQ-ORDERING is NP-complete in general, and we identify a family of instances that can be solved efficiently, the 2-fixed instances. We show that this result serves as a framework for several other problems that can be formulated as instances of SIMULTANEOUS PQ-ORDERING. In particular, we give linear-time algorithms for recognizing simultaneous interval graphs and extending partial interval representations. Moreover, we obtain a linear-time algorithm for PARTIALLY PQ-CONSTRAINED PLANARITY for biconnected graphs, which asks for a planar embedding in the presence of 16 PQ-trees that restrict the possible orderings of edges around vertices, and a quadratic-time algorithm for SIMULTANEOUS EMBEDDING WITH FIXED EDGES for biconnected graphs with a connected intersection. Both results can be extended to the case where the input graphs are not necessarily biconnected but have the property that each cutvertex is contained in at most two nontrivial blocks. This includes, for example, the case where both graphs have a maximum degree of 5.}, author = {Bläsius, Thomas and Rutter, Ignaz}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {thomasblaesius year2013 soda}, pages = {1030-1043}, title = {Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems}, year = 2013 }

2012 [ to top ]

• 
  Bläsius, Thomas; Rutter, IgnazDisconnectivity and Relative Positions in Simultaneous Embeddings. Graph Drawing (GD) 2012: 31-42
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  For two planar graphs \(G^1 = (V^1, E^1)\) and \(G^2 = ( V^2, E^2) \) sharing a common subgraph \(G = G^1 \cap G^2\) the problem Simultaneous Embedding with Fixed Edges (SEFE) asks whether they admit planar drawings such that the common graph is drawn the same. Previous algorithms only work for cases where \(G\) is connected, and hence do not need to handle relative positions of connected components. We consider the problem where \(G, G^1\) and \(G^2\) are not necessarily connected.First, we show that a general instance of SEFE can be reduced in linear time to an equivalent instance where \(V^1 = V^2\) and \(G^1\) and \(G^2\) are connected. Second, for the case where \(G\) consists of disjoint cycles, we introduce the CC-tree which represents all embeddings of \(G\) that extend to planar embeddings of \(G^1\). We show that CC-trees can be computed in linear time, and that their intersection is again a CC-tree. This yields a linear-time algorithm for SEFE if all k input graphs (possibly \(k > 2\)) pairwise share the same set of disjoint cycles. These results, including the CC-tree, extend to the case where \(G\) consists of arbitrary connected components, each with a fixed planar embedding on the sphere. Then the running time is \(O(n^2)\) .
  @inproceedings{DBLP:conf/gd/BlasiusR12, abstract = {For two planar graphs \(G^1 = (V^1, E^1)\) and \(G^2 = ( V^2, E^2) \) sharing a common subgraph \(G = G^1 \cap G^2\) the problem Simultaneous Embedding with Fixed Edges (SEFE) asks whether they admit planar drawings such that the common graph is drawn the same. Previous algorithms only work for cases where \(G\) is connected, and hence do not need to handle relative positions of connected components. We consider the problem where \(G, G^1\) and \(G^2\) are not necessarily connected.First, we show that a general instance of SEFE can be reduced in linear time to an equivalent instance where \(V^1 = V^2\) and \(G^1\) and \(G^2\) are connected. Second, for the case where \(G\) consists of disjoint cycles, we introduce the CC-tree which represents all embeddings of \(G\) that extend to planar embeddings of \(G^1\). We show that CC-trees can be computed in linear time, and that their intersection is again a CC-tree. This yields a linear-time algorithm for SEFE if all k input graphs (possibly \(k > 2\)) pairwise share the same set of disjoint cycles. These results, including the CC-tree, extend to the case where \(G\) consists of arbitrary connected components, each with a fixed planar embedding on the sphere. Then the running time is \(O(n^2)\) .}, author = {Bläsius, Thomas and Rutter, Ignaz}, booktitle = {Graph Drawing (GD)}, keywords = {thomasblaesius year2012 gd}, pages = {31-42}, title = {Disconnectivity and Relative Positions in Simultaneous Embeddings}, year = 2012 }

2010 [ to top ]

• 
  Bläsius, Thomas; Krug, Marcus; Rutter, Ignaz; Wagner, DorotheaOrthogonal Graph Drawing with Flexibility Constraints. Graph Drawing (GD) 2010: 92-104
  [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  @inproceedings{DBLP:conf/gd/BlasiusKRW10, author = {Bläsius, Thomas and Krug, Marcus and Rutter, Ignaz and Wagner, Dorothea}, booktitle = {Graph Drawing (GD)}, keywords = {thomasblaesius gd year2010}, pages = {92-104}, title = {Orthogonal Graph Drawing with Flexibility Constraints}, year = 2010 }