Search

We study the planar orthogonal drawing style within the framework of partial representation extension. Let $(G,H,{\Gamma}_H )$ be a partial orthogonal drawing, i.e., G is a graph, $H\subseteq G$ is a subgraph and ${\Gamma}_H$ is a planar orthogonal drawing of H. We show that the existence of an orthogonal drawing ${\Gamma}_G$ of $G$ that extends ${\Gamma}_H$ can be tested in linear time. If such a drawing exists, then there also is one that uses $O(|V(H)|)$ bends per edge. On the other hand, we show that it is NP-complete to find an extension that minimizes the number of bends or has a fixed number of bends per edge., Comment: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

In this article, we consider the rectilinear crossing minimization problem , i.e., we seek a straight-line drawing Γ of a graph G =( V , E ) with a small number of edge crossings. Crossing minimization is an active field of research [1, 10]. While there is a lot of work on heuristics for topological drawings, these techniques are typically not transferable to the rectilinear (i.e., straight-line) setting. We introduce and evaluate three heuristics for rectilinear crossing minimization. The approaches are based on the primitive operation of moving a single vertex to its crossing-minimal position in the current drawing Γ, for which we give an O (( kn + m ) 2 log ( kn + m ))-time algorithm, where k is the degree of the vertex and n and m are the number of vertices and edges of the graph, respectively. In an experimental evaluation, we demonstrate that our algorithms compute straight-line drawings with fewer crossings than energy-based algorithms implemented in the O pen G raph D rawing F ramework [11] on a varied set of benchmark instances. Additionally, we show that the difference of the number of crossings of topological drawings computed with the edge insertion approach [10, 13] and the number of crossings in straight-line drawings computed by our heuristic is relatively small. All experiments are evaluated with a statistical significance level of α = 0.05.

We study the interplay between embedding constrained planarity and hybrid planarity testing. We consider a constrained planarity testing problem, called 1-Fixed Constrained Planarity, and prove that this problem can be solved in quadratic time for biconnected graphs. Our solution is based on a new definition of fixedness that makes it possible to simplify and extend known techniques about Simultaneous PQ-Ordering. We apply these results to different variants of hybrid planarity testing, including a relaxation of NodeTrix Planarity with fixed sides, that allows rows and columns to be independently permuted.

We study level planarity testing of graphs with a fixed combinatorial embedding for three different notions of combinatorial embeddings, namely the level embedding, the upward embedding and the planar embedding. These notions allow for increasing degrees of freedom in their corresponding drawings. For the fixed level embedding there are known and easy to test level planarity criteria. We use these criteria to prove an "untangling" lemma that plays a key role in a simple level planarity test for the case where only the upward embedding is fixed. This test is then adapted to the case where only the planar embedding is fixed. Further, we characterize radial upward planar embeddings, which lets us extend our results to radial level planarity. No algorithms were previously known for these problems.

In this paper we settle the computational complexity of two open problems related to the extension of the notion of level planarity to surfaces different from the plane. Namely, we show that the problems of testing the existence of a level embedding of a level graph on the surface of the rolling cylinder or on the surface of the torus, respectively known by the name of Cyclic Level Planarity and Torus Level Planarity , are polynomial-time solvable. Moreover, we show a complexity dichotomy for testing the Simultaneous Level Planarity of a set of level graphs, with respect to both the number of level graphs and the number of levels.

We study the planar orthogonal drawing style within the framework of partial representation extension. Let \((G,H,\varGamma _H)\) be a partial orthogonal drawing, i.e., G is a graph, \(H\subseteq G\) is a subgraph and \(\varGamma _H\) is a planar orthogonal drawing of H.

We consider drawings of graphs that contain dense subgraphs. We introduce intersection-link representations for such graphs, in which each vertex $u$ is represented by a geometric object $R(u)$ and in which each edge $(u,v)$ is represented by the intersection between $R(u)$ and $R(v)$ if it belongs to a dense subgraph or by a curve connecting the boundaries of $R(u)$ and $R(v)$ otherwise. We study a notion of planarity, called Clique Planarity, for intersection-link representations of graphs in which the dense subgraphs are cliques., 15 pages, 8 figures, extended version of 'Intersection-Link Representations of Graphs' (23rd International Symposium on Graph Drawing, 2015)

Contraction hierarchies are a speed-up technique to improve the performance of shortest-path computations, which works very well in practice. Despite convincing practical results, there is still a lack of theoretical explanation for this behavior.In this paper, we develop a theoretical framework for studying search space sizes in contraction hierarchies. We prove the first bounds on the size of search spaces that depend solely on structural parameters of the input graph, that is, they are independent of the edge lengths. To achieve this, we establish a connection with the well-studied elimination game. Our bounds apply to graphs with treewidth k, and to any minor-closed class of graphs that admits small separators. For trees, we show that the maximum search space size can be minimized efficiently, and the average size can be approximated efficiently within a factor of 2.We show that, under a worst-case assumption on the edge lengths, our bounds are comparable to those in the recent paper "VC-Dimension and Shortest Path Algorithms" of Abraham et al. 1, whose analysis depends also on the edge lengths. As a side result, we link their notion of highway dimension (a parameter that is conjectured to be small, but is unknown for all practical instances) with the notion of pathwidth. This is the first relation of highway dimension with a well-known graph parameter.

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 [1] . On the other hand, FlexDraw can be solved efficiently if flex ( e ) ≥ 1 [2] and is trivial if flex ( e ) ≥ 2 [3] for every edge e. To close the gap between the NP-hardness for flex ( e ) = 0 and the efficient algorithm for flex ( e ) ≥ 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 e > 0 FlexDraw is NP-complete for instances with O ( n e ) inflexible edges with pairwise distance Ω ( n 1 − e ) (including the case where they induce a matching), where n denotes the number of vertices in the graph. On the other hand, we give an FPT-algorithm with running time O ( 2 k ⋅ n ⋅ 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.

A simple topological graph is $k$-quasiplanar ($k\geq 2$) if it contains no $k$ pairwise crossing edges, and $k$-planar if no edge is crossed more than $k$ times. In this paper, we explore the relationship between $k$-planarity and $k$-quasiplanarity to show that, for $k \geq 2$, every $k$-planar simple topological graph can be transformed into a $(k+1)$-quasiplanar simple topological graph., Comment: arXiv admin note: substantial text overlap with arXiv:1705.05569

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., Comment: 64 pages, 20 figures

The recently introduced problem of extending partial interval representations asks, for an interval graph with some intervals pre-drawn by the input, whether the partial representation can be extended to a representation of the entire graph. In this paper, we give a linear-time algorithm for extending proper interval representations and an almost quadratic-time algorithm for extending unit interval representations. We also introduce the more general problem of bounded representations of unit interval graphs, where the input constrains the positions of some intervals by lower and upper bounds. We show that this problem is NP-complete for disconnected input graphs and give a polynomial-time algorithm for the special class of instances, where the ordering of the connected components of the input graph along the real line is prescribed. This includes the case of partial representation extension. The hardness result sharply contrasts the recent polynomial-time algorithm for bounded representations of proper interval graphs (Balko et al. in 2013). So unless $${\textsf {P}} = {\textsf {NP}}$$P=NP, proper and unit interval representations have vastly different structure. This explains why partial representation extension problems for these different types of representations require substantially different techniques.

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., 17 pages, 2 figures

Given a plane graph G (i.e., a planar graph with a fixed planar embedding and outer face) and a biconnected subgraph $$G^{\prime }$$Gź with a fixed planar straight-line convex drawing, we consider the question whether this drawing can be extended to a planar straight-line drawing of G. We characterize when this is possible in terms of simple necessary conditions, which we prove to be sufficient. This also leads to a linear-time testing algorithm. If a drawing extension exists, one can be computed in the same running time.

The algorithm to insert an edge e in linear time into a planar graph G with a minimal number of crossings on e [10], is a helpful tool for designing heuristics that minimize edge crossings in drawings of general graphs. Unfortunately, some graphs do not have a geometric embedding \(\varGamma \) such that \(\varGamma +e\) has the same number of crossings as the embedding \(G+e\). This motivates the study of the computational complexity of the following problem: Given a combinatorially embedded graph G, compute a geometric embedding \(\varGamma \) that has the same combinatorial embedding as G and that minimizes the crossings of \(\varGamma +e\). We give polynomial-time algorithms for special cases and prove that the general problem is fixed-parameter tractable in the number of crossings. Moreover, we show how to approximate the number of crossings by a factor \((\varDelta -2)\), where \(\varDelta \) is the maximum vertex degree of G.

Recently, Fulek et al. [1, 2, 3] have presented Hanani-Tutte results for (radial) level planarity, i.e., a graph is (radial) level planar if it admits a (radial) level drawing where any two (independent) edges cross an even number of times. We show that the 2-Sat formulation of level planarity testing due to Randerath et al. [4] is equivalent to the strong Hanani-Tutte theorem for level planarity [3]. Further, we show that this relationship carries over to radial level planarity, which yields a novel polynomial-time algorithm for testing radial level planarity.

In this paper, we study the problem of augmenting a planar graph such that it becomes $$k$$k-regular, $$c$$c-connected and remains planar, either in the sense that the augmented graph is planar, or in the sense that the input graph has a fixed (topological) planar embedding that can be extended to a planar embedding of the augmented graph. We fully classify the complexity of this problem for all values of $$k$$k and $$c$$c in both, the variable embedding and the fixed embedding case. For $$k \le 2$$k≤2 all problems are simple and for $$k \ge 4$$k?4 all problems are NP-complete. Our main results are efficient algorithms (with running time $$O(n^{1.5}))$$O(n1.5)) for deciding the existence of a $$c$$c-connected, 3-regular augmentation of a graph with a fixed planar embedding for $$c=0,1,2$$c=0,1,2 and a corresponding hardness result for $$c=3$$c=3. The algorithms are such that for yes-instances a corresponding augmentation can be constructed in the same running time.

Motivated by drawing route sketches, we consider the d-regular path schematization problem. For this problem we are given an embedded path P (e.g., a route in a road network) and a positive integer d. The goal is to find a d-schematized embedding of P in which the orthogonal order of all vertices in the input is preserved and in which every edge has a direction that is an integer multiple of (90/d)^o. We show that deciding whether a path can be d-schematized is NP-complete for any positive integer d. Despite the NP-hardness of the problem we still want to be able to generate route sketches and thus need to solve the d-regular path schematization problem. We explore two different algorithmic approaches, both of which consider two additional quality constraints: We require that every edge is drawn with a user-specified minimum length and we want to maximize the number of edges that are drawn with their preferred direction. The first algorithmic approach restricts the input paths to be axis-monotone. We show that there exists a polynomial-time algorithm that solves the d-regular path schematization problem for this restricted class of embedded paths. We extend this approach by a heuristic such that it can handle arbitrary simple paths. However, for the second step we cannot guarantee that the orthogonal order of the input embedding is maintained. The second approach is a formulation of the d-regular path schematization problem as a mixed integer linear program. Finally, we give an experimental evaluation which shows that both approaches generate reasonable route sketches for real-world data.

We study contact representations of edge-weighted planar graphs, where vertices are rectangles or rectilinear polygons and edges are polygon contacts whose lengths represent the edge weights. We show that for any given edge-weighted planar graph whose outer face is a quadrangle, that is internally triangulated and that has no separating triangles we can construct in linear time an edge-proportional rectangular dual if one exists and report failure otherwise. For a given combinatorial structure of the contact representation and edge weights interpreted as lower bounds on the contact lengths, a corresponding contact representation that minimizes the size of the enclosing rectangle can be found in linear time. If the combinatorial structure is not fixed, we prove NP-hardness of deciding whether a contact representation with bounded contact lengths exists. Finally, we give a complete characterization of the rectilinear polygon complexity required for representing biconnected internally triangulated graphs: For outerplanar graphs complexity 8 is sufficient and necessary, and for graphs with two adjacent or multiple non-adjacent internal vertices the complexity is unbounded.

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 $\operatorname{flex}: E \longrightarrow\mathbb{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 $\operatorname{flex}(e)$ bends? Note that in our setting the combinatorial embedding of G is not fixed. FlexDraw directly extends the problem β-embeddability asking whether G can be embedded with at most β 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 $\mathcal{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 $\mathcal{NP}$ -hard even if the edges with flexibility 0 induce a tree or a union of disjoint stars.

We derive a variety of results on the algorithmics of switch graphs. On the negative side we prove hardness of the following problems: Given a switch graph, does it possess a bipartite/planar/triangle-free/Eulerian configuration? On the positive side we design fast algorithms for several connectivity problems in undirected switch graphs, and for recognizing acyclic configurations in directed switch graphs.

We consider a framework for bi-objective network construction problems where one objective is to be maximized while the other is to be minimized. Given a host graph G=(V,E) with edge weights w e ?? and edge lengths l e ?? for e?E we define the density of a pattern subgraph H=(V?,E?)⊆G as the ratio ?(H)=? e?E? w e /? e?E? l e . We consider the problem of computing a maximum density pattern H under various additional constraints. In doing so, we compute a single Pareto-optimal solution with the best weight per cost ratio subject to additional constraints further narrowing down feasible solutions for the underlying bi-objective network construction problem. First, we consider the problem of computing a maximum density pattern with weight at least W and length at most L in a host G. We call this problem the biconstrained density maximization problem. This problem can be interpreted in terms of maximizing the return on investment for network construction problems in the presence of a limited budget and a target profit. We consider this problem for different classes of hosts and patterns. We show that it is NP-hard, even if the host has treewidth 2 and the pattern is a path. However, it can be solved in pseudo-polynomial linear time if the host has bounded treewidth and the pattern is a graph from a given minor-closed family of graphs. Finally, we present an FPTAS for a relaxation of the density maximization problem, in which we are allowed to violate the upper bound on the length at the cost of some penalty. Second, we consider the maximum density subgraph problem under structural constraints on the vertex set that is used by the patterns. While a maximum density perfect matching can be computed efficiently in general graphs, the maximum density Steiner-subgraph problem, which requires a subset of the vertices in any feasible solution, is NP-hard and unlikely to admit a constant-factor approximation. When parameterized by the number of vertices of the pattern, this problem is W[1]-hard in general graphs. On the other hand, it is FPT on planar graphs if there is no constraint on the pattern and on general graphs if the pattern is a path.

In this paper, we present algorithms that compute large matchings in planar graphs with fixed minimum degree. The algorithms give a guarantee on the size of the computed matching and run in linear time. Thus they are faster than the best known algorithm for computing maximum matchings in general graphs and in planar graphs, which run in O(nm) and O(n1.188) time, respectively. For the class of planar graphs with minimum degree 3, the bounds we achieve are known to be the best possible. Further, we discuss how minimum degree 5 can be used to obtain stronger bounds on the matching size.

Motivated by finding planar embeddings that lead to drawings with favorable aesthetics, we study the problems MINMAXFACE and UNIFORMFACES of embedding a given biconnected multi-graph such that the largest face is as small as possible and such that all faces have the same size, respectively. We prove a complexity dichotomy for MINMAXFACE and show that deciding whether the maximum is at most $k$ is polynomial-time solvable for $k \leq 4$ and NP-complete for $k \geq 5$. Further, we give a 6-approximation for minimizing the maximum face in a planar embedding. For UNIFORMFACES, we show that the problem is NP-complete for odd $k \geq 7$ and even $k \geq 10$. Moreover, we characterize the biconnected planar multi-graphs admitting 3- and 4-uniform embeddings (in a $k$-uniform embedding all faces have size $k$) and give an efficient algorithm for testing the existence of a 6-uniform embedding., Comment: 23 pages, 5 figures, extended version of 'Planar Embeddings with Small and Uniform Faces' (The 25th International Symposium on Algorithms and Computation, 2014)

Given a planar graph $G$ and a partition of the neighbors of each vertex $v$ in four sets $UR(v)$, $UL(v)$, $DL(v)$, and $DR(v)$, the problem Windrose Planarity asks to decide whether $G$ admits a windrose-planar drawing, that is, a planar drawing in which (i) each neighbor $u \in UR(v)$ is above and to the right of $v$, (ii) each neighbor $u \in UL(v)$ is above and to the left of $v$, (iii) each neighbor $u \in DL(v)$ is below and to the left of $v$, (iv) each neighbor $u \in DR(v)$ is below and to the right of $v$, and (v) edges are represented by curves that are monotone with respect to each axis. By exploiting both the horizontal and the vertical relationship among vertices, windrose-planar drawings allow to simultaneously visualize two partial orders defined by means of the edges of the graph. Although the problem is NP-hard in the general case, we give a polynomial-time algorithm for testing whether there exists a windrose-planar drawing that respects a given combinatorial embedding. This algorithm is based on a characterization of the plane triangulations admitting a windrose-planar drawing. Furthermore, for any embedded graph with $n$ vertices that has a windrose-planar drawing, we can construct one with at most one bend per edge and with at most $2n-5$ bends in total, which lies on the $3n \times 3n$ grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area., Appeared in Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)

In this paper we introduce a notion of planarity for graphs that are presented in a streaming fashion. A $\textit{streamed graph}$ is a stream of edges $e_1,e_2,...,e_m$ on a vertex set $V$. A streamed graph is $\omega$-$\textit{stream planar}$ with respect to a positive integer window size $\omega$ if there exists a sequence of planar topological drawings $\Gamma_i$ of the graphs $G_i=(V,\{e_j \mid i\leq j < i+\omega\})$ such that the common graph $G^{i}_\cap=G_i\cap G_{i+1}$ is drawn the same in $\Gamma_i$ and in $\Gamma_{i+1}$, for $1\leq i < m-\omega$. The $\textit{Stream Planarity}$ Problem with window size $\omega$ asks whether a given streamed graph is $\omega$-stream planar. We also consider a generalization, where there is an additional $\textit{backbone graph}$ whose edges have to be present during each time step. These problems are related to several well-studied planarity problems. We show that the $\textit{Stream Planarity}$ Problem is NP-complete even when the window size is a constant and that the variant with a backbone graph is NP-complete for all $\omega \ge 2$. On the positive side, we provide $O(n+\omega{}m)$-time algorithms for (i) the case $\omega = 1$ and (ii) all values of $\omega$ provided the backbone graph consists of one $2$-connected component plus isolated vertices and no stream edge connects two isolated vertices. Our results improve on the Hanani-Tutte-style $O((nm)^3)$-time algorithm proposed by Schaefer [GD'14] for $\omega=1$., Comment: 21 pages, 9 figures, extended version of "Planarity of Streamed Graphs" (9th International Conference on Algorithms and Complexity, 2015)

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, $$\varTheta 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, $$\varTheta n^2$$ voxels are always sufficient and sometimes necessary for any n-vertex graph. We improve this bound to $$\varTheta n\cdot \tau $$ for graphs of treewidthi¾?$$\tau $$ and to $$Og+1^2n\log ^2n$$ for graphs of genus g. In particular, planar graphs admit representations with $$On\log ^2n$$ voxels.

A greedily routable region (GRR) is a closed subset of $\mathbb R^2$, in which each destination point can be reached from each starting point by choosing the direction with maximum reduction of the distance to the destination in each point of the path. Recently, Tan and Kermarrec proposed a geographic routing protocol for dense wireless sensor networks based on decomposing the network area into a small number of interior-disjoint GRRs. They showed that minimum decomposition is NP-hard for polygons with holes. We consider minimum GRR decomposition for plane straight-line drawings of graphs. Here, GRRs coincide with self-approaching drawings of trees, a drawing style which has become a popular research topic in graph drawing. We show that minimum decomposition is still NP-hard for graphs with cycles, but can be solved optimally for trees in polynomial time. Additionally, we give a 2-approximation for simple polygons, if a given triangulation has to be respected., Comment: full version of a paper appearing in ISAAC 2015

A map graph is a contact graph of internally-disjoint regions of the plane, where the contact can be even a point. Namely, each vertex is represented by a simple connected region and two vertices are connected by an edge iff the corresponding regions touch.

We consider the problem of creating plane orthogonal drawings of 4-planar graphs planar graphs with maximum degreei¾ź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$$i¾ź[7]. On the other hand, FlexDraw can be solved efficiently if $${{\mathrm{flex}}}e \ge 1$$i¾ź[2] and is trivial if $${{\mathrm{flex}}}e \ge 2$$i¾ź[1] 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 flexibilityi¾ź$$0$$. We show that for any $$\varepsilon > 0$$ FlexDraw is NP-complete for instances with $$On^\varepsilon $$ inflexible edges with pairwise distance $$\Omega n^{1-\varepsilon }$$ including the case where they induce a matching. On the other hand, we give an FPT-algorithm with running time $$O2^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 degreei¾ź4.

We consider the following problem of labeling points in a dynamic map that allows rotation. We are given a set of points in the plane labeled by a set of mutually disjoint labels, where each label is an axis-aligned rectangle attached with one corner to its respective point. We require that each label remains horizontally aligned during the map rotation and our goal is to find a set of mutually non-overlapping active labels for every rotation angle $\alpha \in [0, 2\pi)$ so that the number of active labels over a full map rotation of 2$\pi$ is maximized. We discuss and experimentally evaluate several labeling models that define additional consistency constraints on label activities in order to reduce flickering effects during monotone map rotation. We introduce three heuristic algorithms and compare them experimentally to an existing approximation algorithm and exact solutions obtained from an integer linear program. Our results show that on the one hand low flickering can be achieved at the expense of only a small reduction in the objective value, and that on the other hand the proposed heuristics achieve a high labeling quality significantly faster than the other methods., Comment: 16 pages, extended version of a SEA 2014 paper

The recently introduced problem of extending partial interval representations asks, for an interval graph with some intervals pre-drawn by the input, whether the partial representation can be extended to a representation of the entire graph. In this paper, we give a linear-time algorithm for extending proper interval representations and an almost quadratic-time algorithm for extending unit interval representations.

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 (allowing 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.

An st-path in a drawing of a graph is self-approaching if during a traversal of the corresponding curve from s to any point t' on the curve the distance to t' is non-increasing. A path has increasing chords if it is self-approaching in both directions. A drawing is self-approaching increasing-chord if any pair of vertices is connected by a self-approaching increasing-chord path. We study self-approaching and increasing-chord drawings of triangulations and 3-connected planar graphs. We show that in the Euclidean plane, triangulations admit increasing-chord drawings, and for planar 3-trees we can ensure planarity. Moreover, we give a binary cactus that does not admit a self-approaching drawing. Finally, we show that 3-connected planar graphs admit increasing-chord drawings in the hyperbolic plane and characterize the trees that admit such drawings.

We consider the following problem of labeling points in a dynamic map that allows rotation. We are given a set of points in the plane labeled by a set of mutually disjoint labels, where each label is an axis-aligned rectangle attached with one corner to its respective point. We require that each label remains horizontally aligned during the map rotation and our goal is to find a set of mutually non-overlapping active labels for every rotation angle α ∈ [0,2π) so that the number of active labels over a full map rotation of 2π is maximized. We discuss and experimentally evaluate several labeling models that define additional consistency constraints on label activities in order to reduce flickering effects during monotone map rotation. We introduce three heuristic algorithms and compare them experimentally to an existing approximation algorithm and exact solutions obtained from an integer linear program. Our results show that on the one hand low flickering can be achieved at the expense of only a small reduction in the objective value, and that on the other hand the proposed heuristics achieve a high labeling quality significantly faster than the other methods.

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$., 14 pages, 6 figures

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 ${\rm cost}_{e}: \mathbb{N}_{0} \longrightarrow \mathbb{R}$ defining costs depending on the number of bends e has, compute an 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 ·Tflow(n)) and O(n2 ·Tflow(n)) for biconnected and connected graphs, respectively, where Tflow(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.

We study contact representations of edge-weighted planar graphs, where vertices are rectangles or rectilinear polygons and edges are polygon contacts whose lengths represent the edge weights. We show that for any given edge-weighted planar graph whose outer face is a quadrangle, that is internally triangulated and that has no separating triangles we can construct in linear time an edge-proportional rectangular dual if one exists and report failure otherwise. For a given combinatorial structure of the contact representation and edge weights interpreted as lower bounds on the contact lengths, a corresponding contact representation that minimizes the size of the enclosing rectangle can be found in linear time. If the combinatorial structure is not fixed, we prove NP-hardness of deciding whether a contact representation with bounded contact lengths exists. Finally, we give a complete characterization of the rectilinear polygon complexity required for representing biconnected internally triangulated graphs: For outerplanar graphs complexity 8 is sufficient and necessary, and for graphs with two adjacent or multiple non-adjacent internal vertices the complexity is unbounded.

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.

We consider orthogonal upward drawings of directed acyclic graphs (DAGs) with nodes of uniform width but node-specific height. One way to draw such graphs is to use a layering technique as provided by the Sugiyama framework [10]. However, to avoid drawbacks of the Sugiyama framework we use the layer-free upward crossing minimization algorithm suggested by Chimani et al. and integrate it into the topology-shape-metric (TSM) framework introduced by Tamassia [11]. This in combination with an algorithm by Biedl and Kant [2] lets us generate column-based layouts, i.e., layouts where the plane is divided into uniform-width columns and every node is assigned to a column. We show that our column-based approach allows to generate visually appealing, compact layouts with few edge crossing and at most four bends per edge. Furthermore, the resulting layouts exhibit a high degree of symmetry and implicitly support edge bundling. We justify our approach by an experimental evaluation based on real-world examples.

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.

In this paper we study many-to-one boundary labeling with backbone leaders. In this model, a horizontal backbone reaches out of each label into the feature-enclosing rectangle. Feature points associated with this label are linked via vertical line segments to the backbone. We present algorithms for label number and leader-length minimization. If crossings are allowed, we aim to minimize their number. This can be achieved efficiently in the case of fixed label order. We show that the corresponding problem in the case of flexible label order is NP-hard.

For two planar graph $G^{\textcircled1}$ = ($V^{\textcircled1}$, $E^{\textcircled1}$) and $G^{\textcircled2}$ = ($V^{\textcircled2}$, $E^{\textcircled2}$) sharing a common subgraph G = $G^{\textcircled1}$ ∩ $G^{\textcircled2}$ 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^{\textcircled1}$ and $G^{\textcircled2}$ 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^{\textcircled1}$ = $V^{\textcircled2}$ and $G^{\textcircled1}$ and $G^{\textcircled2}$ 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^{\textcircled1}$. 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 embedding. Then the running time is O(n2).

In the Boundary Labeling problem, we are given a set of n points, referred to as sites, inside an axis-parallel rectangle R, and a set of n pairwise disjoint rectangular labels that are attached to R from the outside. The task is to connect the sites to the labels by non-intersecting rectilinear paths, so-called leaders, with at most one bend. In this paper, we study the problem Two-Sided Boundary Labeling with Adjacent Sides, where labels lie on two adjacent sides of the enclosing rectangle. We present a polynomial-time algorithm that computes a crossing-free leader layout if one exists. So far, such an algorithm has only been known for the cases that labels lie on one side or on two opposite sides of R (where a crossing-free solution always exists). For the more difficult case where labels lie on adjacent sides, we show how to compute crossing-free leader layouts that maximize the number of labeled points or minimize the total leader length.

Contraction hierarchies are a speed-up technique to improve the performance of shortest-path computations, which works very well in practice. Despite convincing practical results, there is still a lack of theoretical explanation for this behavior. In this paper, we develop a theoretical framework for studying search space sizes in contraction hierarchies. We prove the first bounds on the size of search spaces that depend solely on structural parameters of the input graph, that is, they are independent of the edge lengths. To achieve this, we establish a connection with the well-studied elimination game. Our bounds apply to graphs with treewidth k, and to any minor-closed class of graphs that admits small separators. For trees, we show that the maximum search space size can be minimized efficiently, and the average size can be approximated efficiently within a factor of 2. We show that, under a worst-case assumption on the edge lengths, our bounds are comparable to the recent results of Abraham et al. [1], whose analysis depends also on the edge lengths. As a side result, we link their notion of highway dimension (a parameter that is conjectured to be small, but is unknown for all practical instances) with the notion of pathwidth. This is the first relation of highway dimension with a well-known graph parameter.

A partially embedded graph (or PEG) is a triple (G,H,\H), where G is a graph, H is a subgraph of G, and \H is a planar embedding of H. We say that a PEG (G,H,\H) is planar if the graph G has a planar embedding that extends the embedding \H. We introduce a containment relation of PEGs analogous to graph minor containment, and characterize the minimal non-planar PEGs with respect to this relation. We show that all the minimal non-planar PEGs except for finitely many belong to a single easily recognizable and explicitly described infinite family. We also describe a more complicated containment relation which only has a finite number of minimal non-planar PEGs. Furthermore, by extending an existing planarity test for PEGs, we obtain a polynomial-time algorithm which, for a given PEG, either produces a planar embedding or identifies an obstruction., 45 pages, 18 figures

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)., 31 pages, 14 figures

Motivated by the problem in [6], which studies the relative efficiency of propositional proof systems, 2-edge colorings of complete bipartite graphs are investigated. It is shown that if the edges of $G=K_{n,n}$ are colored with black and white such that the number of black edges differs from the number of white edges by at most 1, then there are at least $n(1-1/\sqrt{2})$ vertex-disjoint forks with centers in the same partite set of $G$. Here, a fork is a graph formed by two adjacent edges of different colors. The bound is sharp. Moreover, an algorithm running in time $O(n^2 \log n \sqrt{n \alpha(n^2,n) \log n})$ and giving a largest such fork forest is found., Comment: 5 pages, 3 figures

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., Comment: 34 pages, 8 figures

In this work we consider the following problem. Given a planar graph G with maximum degree 4 and a function flex : E → N0 that gives each edge a flexibility. 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. We give a polynomial-time algorithm for this problem when the flexibility of each edge is positive. This includes as a special case the problem of deciding whether G admits a drawing with at most one bend per edge.