BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Thomas Bläsius

Thomas Bläsius appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsDiscrete Mathematicsmath.COComputational GeometryComputational ComplexityComputer Science and Game Theorymath.PR

Catalog footprint

What is connected

19works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

19 published item(s)

preprint2023arXiv

Recognizing Unit Disk Graphs in Hyperbolic Geometry is $\exists\mathbb{R}$-Complete

A graph G is a (Euclidean) unit disk graph if it is the intersection graph of unit disks in the Euclidean plane $\mathbb{R}^2$. Recognizing them is known to be $\exists\mathbb{R}$-complete, i.e., as hard as solving a system of polynomial inequalities. In this note we describe a simple framework to translate $\exists\mathbb{R}$-hardness reductions from the Euclidean plane $\mathbb{R}^2$ to the hyperbolic plane $\mathbb{H}^2$. We apply our framework to prove that the recognition of unit disk graphs in the hyperbolic plane is also $\exists\mathbb{R}$-complete.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry

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 $\mathcal {\tilde O}(n^{2 - 1/α} + n^{1/(2α)} + δ_{\max})$ with high probability, where $α\in (0.5, 1)$ controls the power-law exponent of the degree distribution, and $δ_{\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.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

The Flip Schelling Process on Random Geometric and Erdös-Rényi Graphs

Schelling's classical segregation model gives a coherent explanation for the wide-spread phenomenon of residential segregation. We consider an agent-based saturated open-city variant, the Flip Schelling Process (FSP), in which agents, placed on a graph, have one out of two types and, based on the predominant type in their neighborhood, decide whether to changes their types; similar to a new agent arriving as soon as another agent leaves the vertex. We investigate the probability that an edge $\{u,v\}$ is monochrome, i.e., that both vertices $u$ and $v$ have the same type in the FSP, and we provide a general framework for analyzing the influence of the underlying graph topology on residential segregation. In particular, for two adjacent vertices, we show that a highly decisive common neighborhood, i.e., a common neighborhood where the absolute value of the difference between the number of vertices with different types is high, supports segregation and moreover, that large common neighborhoods are more decisive. As an application, we study the expected behavior of the FSP on two common random graph models with and without geometry: (1) For random geometric graphs, we show that the existence of an edge $\{u,v\}$ makes a highly decisive common neighborhood for $u$ and $v$ more likely. Based on this, we prove the existence of a constant $c > 0$ such that the expected fraction of monochrome edges after the FSP is at least $1/2 + c$. (2) For Erdös-Rényi graphs we show that large common neighborhoods are unlikely and that the expected fraction of monochrome edges after the FSP is at most $1/2 + o(1)$. Our results indicate that the cluster structure of the underlying graph has a significant impact on the obtained segregation strength.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Strategic Routing Framework and Algorithms for Computing Alternative Paths

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 of our algorithms serves 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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Efficiently Computing Maximum Flows in Scale-Free Networks

We study the maximum-flow/minimum-cut problem on scale-free networks, i.e., graphs whose degree distribution follows a power-law. We propose a simple algorithm that capitalizes on the fact that often only a small fraction of such a network is relevant for the flow. At its core, our algorithm augments Dinitz's algorithm with a balanced bidirectional search. Our experiments on a scale-free random network model indicate sublinear run time. On scale-free real-world networks, we outperform the commonly used highest-label Push-Relabel implementation by up to two orders of magnitude. Compared to Dinitz's original algorithm, our modifications reduce the search space, e.g., by a factor of 275 on an autonomous systems graph. Beyond these good run times, our algorithm has an additional advantage compared to Push-Relabel. The latter computes a preflow, which makes the extraction of a minimum cut potentially more difficult. This is relevant, for example, for the computation of Gomory-Hu trees. On a social network with 70000 nodes, our algorithm computes the Gomory-Hu tree in 3 seconds compared to 12 minutes when using Push-Relabel.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Local and Union Boxicity

The boxicity $\operatorname{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 $\mathbb{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, Discrete Mathematics 339 (2016)) to define two new parameters: the local boxicity $\operatorname{box}_\ell(H)$ and the union boxicity $\overline{\operatorname{box}}(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 $\operatorname{box}_\ell(H) \leq \overline{\operatorname{box}}(H) \leq \operatorname{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 $\mathbb{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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Scalable Isocontour Visualization in Road Networks via Minimum-Link Paths

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 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 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, answering queries in a few milliseconds on average even for long ranges.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A New Perspective on Clustered Planarity as a Combinatorial Embedding Problem

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Disconnectivity and Relative Positions in Simultaneous Embeddings

The problem Simultaneous Embedding with Fixed Edges (SEFE) asks for two planar graph $G^1 = (V^1, E^1)$ and $G^2 = (V^2, E^2)$ sharing a common subgraph $G = G^1 \cap G^2$ whether they admit planar drawings such that the common graph is drawn the same in both. Previous results on this problem require $G$, $G^1$ and $G^2$ to be connected. This paper is a first step towards solving instances where these graphs are disconnected. First, we show that an instance of the general SEFE-problem can be reduced in linear time to an equivalent instance where $V^1 = V^2$ and $G^1$ and $G^2$ are connected. This shows that it can be assumed without loss of generality that both input graphs are connected. Second, we consider instances where $G$ is disconnected. We show that SEFE can be solved in linear time if $G$ is a family of disjoint cycles by introducing the CC-tree, which represents all simultaneous embeddings. We extend these results (including the CC-tree) to the case where $G$ consists of arbitrary connected components, each with a fixed embedding. Note that previous results require $G$ to be connected and thus do not need to care about relative positions of connected components. By contrast, we assume the embedding of each connected component to be fixed and thus focus on these relative positions. As SEFE requires to deal with both, embeddings of connected components and their relative positions, this complements previous work.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Orthogonal Graph Drawing with Inflexible Edges

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 $\mathrm{flex}(e)$, its flexibility. The problem FlexDraw asks whether there exists an orthogonal drawing such that each edge $e$ has at most $\mathrm{flex}(e)$ bends. It is known that FlexDraw is NP-hard if $\mathrm{flex}(e) = 0$ for every edge $e$. On the other hand, FlexDraw can be solved efficiently if $\mathrm{flex}(e) \ge 1$ and is trivial if $\mathrm{flex}(e) \ge 2$ for every edge $e$. To close the gap between the NP-hardness for $\mathrm{flex}(e) = 0$ and the efficient algorithm for $\mathrm{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 $\varepsilon > 0$ FlexDraw is NP-complete for instances with $O(n^\varepsilon)$ inflexible edges with pairwise distance $Ω(n^{1-\varepsilon})$ (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_{\mathrm{flow}}(n))$, where $T_{\mathrm{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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Pixel and Voxel Representations of Graphs

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, $Θ(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, $Θ(n^2)$ voxels are always sufficient and sometimes necessary for any $n$-vertex graph. We improve this bound to $Θ(n\cdot τ)$ for graphs of treewidth $τ$ and to $O((g+1)^2n\log^2n)$ for graphs of genus $g$. In particular, planar graphs admit representations with $O(n\log^2n)$ voxels.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Simultaneous Embedding of Planar Graphs

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices

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 $μ$ 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 three graphs pairwise intersecting in the same common graph.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Using ILP/SAT to determine pathwidth, visibility representations, and other grid-based graph drawings

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky Model

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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Testing Mutual Duality of Planar Graphs

We introduce and study the problem \mpd, which asks for two planar graphs $G_1$ and $G_2$ whether $G_1$ can be embedded such that its dual is isomorphic to $G_2$. Our algorithmic main result is an NP-completeness proof for the general case and a linear-time algorithm for biconnected graphs. To shed light onto the combinatorial structure of the duals of a planar graph, we consider the \emph{common dual relation} $\sim$, where $G_1 \sim G_2$ if and only if they have a common dual. While $\sim$ is generally not transitive, we show that the restriction to biconnected graphs is an equivalence relation. In this case, being dual to each other carries over to the equivalence classes, i.e., two graphs are dual to each other if and only if any two elements of their respective equivalence classes are dual to each other. To achieve the efficient testing algorithm for \mpd on biconnected graphs, we devise a succinct representation of the equivalence class of a biconnected planar graph. It is similar to SPQR-trees and represents exactly the graphs that are contained in the equivalence class. The testing algorithm then works by testing in linear time whether two such representations are isomorphic. We note that a special case of \mpd is testing whether a graph $G$ is self-dual. Our algorithm handles the case where $G$ is biconnected and our NP-hardness proof extends to testing self-duality of general planar graphs and also to testing map self-duality, where a graph $G$ is map self-dual if it admits a planar embedding $\mathcal G$ such that $G^\star$ is isomorphic to $G$, and additionally the embedding induced by $\mathcal G$ on $G^\star$ is $\mathcal G$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Optimal Orthogonal Graph Drawing with Convex Bend Costs

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. Moreover, as bend minimization over all planar embeddings is NP-hard, most approaches focus on a fixed planar embedding. We consider the problem OptimalFlexDraw that is defined as follows. Given a planar graph G on n vertices with maximum degree 4 and for each edge e a cost function cost_e : N_0 --> R defining costs depending on the number of bends on e, compute an orthogonal drawing of G of minimum cost. Note that this optimizes over all planar embeddings of the input graphs, and the cost functions allow fine-grained control on the bends of edges. 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 (which is a condition similar to the positive flexibility for the decision problem FlexDraw). Moreover, we show the existence of an optimal solution with at most three bends per edge except for a single edge per block (maximal biconnected component) with up to four bends. For biconnected graphs we obtain a running time of O(n T_flow(n)), where T_flow(n) denotes the time necessary to compute a minimum-cost flow in a planar flow network with multiple sources and sinks. For connected graphs that are not biconnected we need an additional factor of O(n).

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems

In this paper, we define and study the new problem 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 that it is efficiently solvable for a special subset of instances, the 2-fixed instances. We then show that several constrained embedding problems can be formulated as such 2-fixed instances. In particular, we obtain a linear-time algorithm for Partially PQ-Constrained Planarity for biconnected graphs, a common generalization of two recently considered embedding problems, and a quadratic-time algorithm for Simultaneous Embedding with Fixed Edges for biconnected graphs with a connected intersection; formerly only the much more restricted case that the intersection is biconnected was known to be efficiently solvable. 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 non-trivial blocks. This includes for example the case where both graphs have maximum degree 5. Moreover, we give an optimal linear-time algorithm for recognition of simultaneous interval graphs, improving upon a recent O(n^2 log n)-time algorithm due to Jampani and Lubiw and show that this can be used to also solve the problem of extending partial interval representations of graphs with n vertices and m edges in time O(n + m), improving a recent result of Klavík et al.

0 citations0 reviewsNo code linkedOpen access