1,720,979 research outputs found
SEFE = C-planarity?
No full textIn this article, we deepen the understanding of the connection between two long-standing graph drawing open problems, Simultaneous Embedding with Fixed Edges (SEFE-2) and Clustered Planarity (C-Planarity). Given two planar graphs on the same set of vertices, the SEFE-2 problem asks to find planar drawings of the two graphs such that each vertex lies on the same point and each common edge is represented by the same curve in both drawings. Given a planar graph together with a recursive clustering of its vertices, the C-Planarity problem asks to find a planar drawing of the graph and a representation of each cluster as a simple region enclosing all and only the vertices of the cluster such that no unnecessary intersection involving clusters and edges is created. In a recent article at GD'12, Marcus Schaefer presented a reduction from C-Planarity to SEFE-2. We prove that a reduction exists also in the opposite direction, if we restrict to instances of SEFE-2 in which the graph induced by the common edges is connected. We pose as an intriguing open question whether the two problems are polynomial-time equivalent
Planarity of streamed graphs
No full textIn this paper we introduce a notion of planarity for graphs that are presented in a streaming fashion. A streamed graph is a stream of edges e1,e2,...,em on a vertex set V. A streamed graph is ω-stream planar with respect to a positive integer window size ω if there exists a sequence of planar topological drawings Γi of the graphs Gi=(V,ej|i≤
On Planar Greedy Drawings of 3-Connected Planar Graphs
No full textA graph drawing is greedy if, for every ordered pair of vertices (x, y), there is a path from x to y such that the Euclidean distance to y decreases monotonically at every vertex of the path. Greedy drawings support a simple geometric routing scheme, in which any node that has to send a packet to a destination “greedily” forwards the packet to any neighbor that is closer to the destination than itself, according to the Euclidean distance in the drawing. In a greedy drawing such a neighbor always exists and hence this routing scheme is guaranteed to succeed. In 2004 Papadimitriou and Ratajczak stated two conjectures related to greedy drawings. The greedy embedding conjecture states that every 3-connected planar graph admits a greedy drawing. The convex greedy embedding conjecture asserts that every 3-connected planar graph admits a planar greedy drawing in which the faces are delimited by convex polygons. In 2008 the greedy embedding conjecture was settled in the positive by Leighton and Moitra. In this paper we prove that every 3-connected planar graph admits a planar greedy drawing. Apart from being a strengthening of Leighton and Moitra’s result, this theorem constitutes a natural intermediate step towards a proof of the convex greedy embedding conjecture
C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width
No full textFor a clustered graph, i.e, a graph whose vertex set is recursively partitioned into clusters, the C-Planarity Testing problem asks whether it is possible to find a planar embedding of the graph and a representation of each cluster as a region homeomorphic to a closed disk such that (1) the subgraph induced by each cluster is drawn in the interior of the corresponding disk, (2) each edge intersects any disk at most once, and (3) the nesting between clusters is reflected by the representation, i.e., child clusters are properly contained in their parent cluster. The computational complexity of this problem, whose study has been central to the theory of graph visualization since its introduction in 1995 [Feng, Cohen, and Eades, Planarity for clustered graphs, ESA’95], has only been recently settled [Fulek and Tóth, Atomic Embeddability, Clustered Planarity, and Thickenability, to appear at SODA’20]. Before such a breakthrough, the complexity question was still unsolved even when the graph has a prescribed planar embedding, i.e, for embedded clustered graphs. We show that the C-Planarity Testing problem admits a single-exponential single-parameter FPT (resp., XP) algorithm for embedded flat (resp., non-flat) clustered graphs, when parameterized by the carving-width of the dual graph of the input. These are the first FPT and XP algorithms for this long-standing open problem with respect to a single notable graph-width parameter. Moreover, the polynomial dependency of our FPT algorithm is smaller than the one of the algorithm by Fulek and Tóth. In particular, our algorithm runs in quadratic time for flat instances of bounded treewidth and bounded face size. To further strengthen the relevance of this result, we show that an algorithm with running time O(r(n)) for flat instances whose underlying graph has pathwidth 1 would result in an algorithm with running time O(r(n)) for flat instances and with running time O(r(n2) + n2) for general, possibly non-flat, instances
Extending upward planar graph drawings
No full textIn this paper we study the computational complexity of the UPWARD PLANARITY EXTENSION problem, which takes as input an upward planar drawing ΓH of a subgraph H of a directed graph G and asks whether ΓH can be extended to an upward planar drawing of G. Our study fits into the line of research on the extensibility of partial representations, which has recently become a mainstream in Graph Drawing. We show the following results. – First, we prove that the UPWARD PLANARITY EXTENSION problem is NP-complete, even if G has a prescribed upward embedding, the vertex set of H coincides with the one of G, and H contains no edge. – Second, we show that the UPWARD PLANARITY EXTENSION problem can be solved in O(nlogn) time if G is an n-vertex upward planar st-graph. This result improves upon a known O(n2)-time algorithm, which however applies to all n-vertex single-source upward planar graphs. – Finally, we show how to solve in polynomial time a surprisingly difficult version of the UPWARD PLANARITY EXTENSION problem, in which the underlying graph of G is a path or a cycle, G has a prescribed upward embedding, H contains no edges, and no two vertices share the same y-coordinate in ΓH
On the Area Requirements of Planar Greedy Drawings of Triconnected Planar Graphs
No full textIn this paper we study the area requirements of planar greedy drawings of triconnected planar graphs. Cao, Strelzoff, and Sun exhibited a family of subdivisions of triconnected plane graphs and claimed that every planar greedy drawing of the graphs in respecting the prescribed plane embedding requires exponential area. However, we show that every n-vertex graph in actually has a planar greedy drawing respecting the prescribed plane embedding on an grid. This reopens the question whether triconnected planar graphs admit planar greedy drawings on a polynomial-size grid. Further, we provide evidence for a positive answer to the above question by proving that every n-vertex Halin graph admits a planar greedy drawing on an grid. Both such results are obtained by actually constructing drawings that are convex and angle-monotone. Finally, we consider-Schnyder drawings, which are angle-monotone and hence greedy if, and show that there exist planar triangulations for which every-Schnyder drawing with a fixed requires exponential area for any resolution rule
Graph Product Structure for h-Framed Graphs
No full textGraph product structure theory expresses certain graphs as subgraphs of the strong product of much simpler graphs. In particular, an elegant formulation for the corresponding structural theorems involves the strong product of a path and of a bounded treewidth graph, and allows to lift combinatorial results for bounded treewidth graphs to graph classes for which the product structure holds, such as to planar graphs [Dujmović et al., J. ACM, 67(4), 22:1-38, 2020]. In this paper, we join the search for extensions of this powerful tool beyond planarity by considering the h-framed graphs, a graph class that includes 1-planar, optimal 2-planar, and k-map graphs (for appropriate values of h). We establish a graph product structure theorem for h-framed graphs stating that the graphs in this class are subgraphs of the strong product of a path, of a planar graph of treewidth at most 3, and of a clique of size 3⌊h2 ⌋ + ⌊h3 ⌋ - 1. This allows us to improve over the previous structural theorems for 1-planar and k-map graphs. Our results constitute significant progress over the previous bounds on the queue number, non-repetitive chromatic number, and p-centered chromatic number of these graph classes, e.g., we lower the currently best upper bound on the queue number of 1-planar graphs and k-map graphs from 115 to 82 and from ⌊332 (k + 3⌊k2 ⌋-3)⌋ to ⌊332 (3⌊k2 ⌋ + ⌊k3 ⌋ - 1)⌋, respectively. We also employ the product structure machinery to improve the current upper bounds on the twin-width of 1-planar graphs from O(1) to 80. All our structural results are constructive and yield efficient algorithms to obtain the corresponding decompositions
Beyond level planarity: Cyclic, torus, and simultaneous level planarity
No full textIn 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
Upward Planar Morphs
No full textWe prove that, given two topologically-equivalent upward planar straight-line drawings of an n-vertex directed graph G, there always exists a morph between them such that all the intermediate drawings of the morph are upward planar and straight-line. Such a morph consists of O(1) morphing steps if G is a reduced planar st-graph, O(n) morphing steps if G is a planar st-graph, O(n) morphing steps if G is a reduced upward planar graph, and O(n2) morphing steps if G is a general upward planar graph. Further, we show that Ω(n) morphing steps might be necessary for an upward planar morph between two topologically-equivalent upward planar straight-line drawings of an n-vertex path
Morphing Triangle Contact Representations of Triangulations
No full textA morph is a continuous transformation between two representations of a graph. We consider the problem of morphing between contact representations of a plane graph. In an F-contact representation of a plane graph G, vertices are realized by internally disjoint elements from a family F of connected geometric objects. Two such elements touch if and only if their corresponding vertices are adjacent. These touchings also induce the same embedding as in G. In a morph between two F-contact representations we insist that at each time step (continuously throughout the morph) we have an F-contact representation. We focus on the case when F is the family of triangles in R2 that are the lower-right half of axis-parallel rectangles. Such RT-representations exist for every plane graph and right triangles are one of the simplest families of shapes supporting this property. Moreover, they naturally correspond to 3-orientations. Thus, they provide a natural case to study regarding morphs of contact representations of plane graphs. We characterize the pairs of RT-representations admitting a morph between each other via the respective 3-orientations. Our characterization leads to a polynomial-time algorithm to decide whether there is a morph between two RT-representations of an n-vertex plane triangulation, and, if so, computes a morph with O(n2) steps. Each of these steps is a linear morph moving the endpoints of each triangle at constant speed along straight-line trajectories. Our characterization also implies that for 4-connected plane triangulations there is a morph between every pair of RT-representations where the “top-most” triangle in both representations corresponds to the same vertex
- …
