2023 [ nach oben ]

Jansen, Bart M. P.; Khazaliya, Liana; Kindermann, Philipp; Liotta, Giuseppe; Montecchiani, Fabrizio; Simonov, Kirill Upward and Orthogonal Planarity are W[1]-Hard Parameterized by TreewidthGraph Drawing (GD) 2023: 203–217
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Upward planarity testing and Rectilinear planarity testing are central problems in graph drawing. It is known that they are both NP-complete, but XP when parameterized by treewidth. In this paper we show that these two problems are W[1]-hard parameterized by treewidth, which answers open problems posed in two earlier papers. The key step in our proof is an analysis of the All-or-Nothing Flow problem, a generalization of which was used as an intermediate step in the NP-completeness proof for both planarity testing problems. We prove that the flow problem is W[1]-hard parameterized by treewidth on planar graphs, and that the existing chain of reductions to the planarity testing problems can be adapted without blowing up the treewidth. Our reductions also show that the known \(n^{\mathcal{O(tw)}\)-time algorithms cannot be improved to run in time \(n^{o(tw)}\) unless ETH fails.
@inproceedings{DBLP:conf/gd/JansenKKLMS23, abstract = {Upward planarity testing and Rectilinear planarity testing are central problems in graph drawing. It is known that they are both NP-complete, but XP when parameterized by treewidth. In this paper we show that these two problems are W[1]-hard parameterized by treewidth, which answers open problems posed in two earlier papers. The key step in our proof is an analysis of the All-or-Nothing Flow problem, a generalization of which was used as an intermediate step in the NP-completeness proof for both planarity testing problems. We prove that the flow problem is W[1]-hard parameterized by treewidth on planar graphs, and that the existing chain of reductions to the planarity testing problems can be adapted without blowing up the treewidth. Our reductions also show that the known \(n^{\mathcal{O}(tw)}\)-time algorithms cannot be improved to run in time \(n^{o(tw)}\) unless ETH fails.}, author = {Jansen, Bart M. P. and Khazaliya, Liana and Kindermann, Philipp and Liotta, Giuseppe and Montecchiani, Fabrizio and Simonov, Kirill}, booktitle = {Graph Drawing (GD)}, keywords = {gd kirillsimonov year2023}, pages = {203–217}, title = {Upward and Orthogonal Planarity are W[1]-Hard Parameterized by Treewidth}, year = 2023 }

2015 [ nach oben ]

Alam, Md. Jawaherul; Bläsius, Thomas; Rutter, Ignaz; Ueckerdt, Torsten; Wolff, Alexander Pixel and Voxel Representations of GraphsGraph 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 = {GD imported thomas thomasblaesius year2015}, pages = {472-486}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Pixel and Voxel Representations of Graphs}, volume = 9411, year = 2015 }

2014 [ nach oben ]

Bläsius, Thomas; Rutter, Ignaz A New Perspective on Clustered Planarity as a Combinatorial Embedding ProblemGraph 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 = {GD imported thomas thomasblaesius year2014}, 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 [ nach oben ]

Biedl, Therese C.; Bläsius, Thomas; Niedermann, Benjamin; Nöllenburg, Martin; Prutkin, Roman; Rutter, Ignaz Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph DrawingsGraph 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 = {GD imported thomas thomasblaesius year2013}, 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; Karrer, Annette; Rutter, Ignaz Simultaneous Embedding: Edge Orderings, Relative Positions, CutverticesGraph 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 = {GD imported thomas thomasblaesius year2013}, pages = {220-231}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices}, volume = 8242, year = 2013 }

2012 [ nach oben ]

Bläsius, Thomas; Rutter, Ignaz Disconnectivity and Relative Positions in Simultaneous EmbeddingsGraph 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 = {gd thomasblaesius year2012}, pages = {31-42}, title = {Disconnectivity and Relative Positions in Simultaneous Embeddings}, year = 2012 }

2010 [ nach oben ]

Bläsius, Thomas; Krug, Marcus; Rutter, Ignaz; Wagner, Dorothea Orthogonal Graph Drawing with Flexibility ConstraintsGraph 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 = {gd thomasblaesius year2010}, pages = {92-104}, title = {Orthogonal Graph Drawing with Flexibility Constraints}, year = 2010 }