1,721,118 research outputs found
Approximation Algorithms for Facial Cycles in Planar Embeddings
Full text linkConsider the following combinatorial problem: Given a planar graph G and a set of simple cycles C in G, find a planar embedding E of G such that the number of cycles in C that bound a face in E is maximized. This problem, called Max Facial C-Cycles, was first studied by Mutzel and Weiskircher [IPCO '99, http://dx.doi.org/10.1007/3-540-48777-8_27) and then proved NP-hard by Woeginger [Oper. Res. Lett., 2002, http://dx.doi.org/10.1016/S0167-6377(02)00119-0].
We establish a tight border of tractability for Max Facial C-Cycles in biconnected planar graphs by giving conditions under which the problem is NP-hard and showing that strengthening any of these conditions makes the problem polynomial-time solvable. Our main results are approximation algorithms for Max Facial C-Cycles. Namely, we give a 2-approximation for series-parallel graphs and a (4+epsilon)-approximation for biconnected planar graphs. Remarkably, this provides one of the first approximation algorithms for constrained embedding problems
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 ⤠j < i + Ï) such that the common graph Gi â© = Gi â© Gi+1 is drawn the same in Îi and in Îi+1, for 1 ⤠i < mâÏ. THE STREAM PLANARITY Problem with window size Ï asks whether a given streamed graph is Ï-stream planar. We also consider a generalization, where there is an additional 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 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 Ï â¥ 2. On the positive side, we provide O(n + Ïm)-time algorithms for (i) the case Ï = 1 and (ii) all values of Ï 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 Ï = 1
Windrose planarity: Embedding graphs with direction-constrained edges
No full textGiven a planar graph G and a partition of the neighbors of each vertex v in four sets v, v, v, and 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 ∈ v is above and to the right of v, (ii) each neighbor u ∈ v is above and to the left of v, (iii) each neighbor u ∈ v is below and to the left of v, (iv) each neighbor u ∈ 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 us to simultaneously visualize two partial orders defined by means of the edges of the graph. Although the problem is N P-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 × 3n grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area
Windrose planarity: Embedding graphs with direction-constrained edges
No full textGiven a planar graph G(V, E) and a partition of the neighbors of each vertex v σ V in four sets v, v, v, and 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 σ v is above and to the right of v, (ii) each neighbor u σ v is above and to the left of v, (iii) each neighbor u σ v is below and to the left of v, (iv) each neighbor u σ 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 combinatorial embedding that is given as part of the input. This algorithm is based on a characterization of the plane triangulations admitting a windrose-planar drawing. Furthermore, for any embedded graph admitting a windrose-planar drawing we show how to construct one with at most one bend per edge on an 0(n) x 0(n) grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area
Testing Planarity of Partially Embedded Graphs
Full text linkWe study the following problem: given a planar graph G and a planar drawing (embedding) of a subgraph
of G, can such a drawing be extended to a planar drawing of the entire graph G? This problem fits the
paradigm of extending a partial solution for a problem to a complete one, which has been studied before in
many different settings. Unlike many cases, in which the presence of a partial solution in the input makes an
otherwise easy problem hard, we show that the planarity question remains polynomial-time solvable. Our
algorithm is based on several combinatorial lemmas, which show that the planarity of partially embedded
graphs exhibits the ‘TONCAS’ behavior “the obvious necessary conditions for planarity are also sufficient.”
These conditions are expressed in terms of the interplay between (1) the rotation system and containment
relationships between cycles and (2) the decomposition of a graph into its connected, biconnected, and
triconnected components. This implies that no dynamic programming is needed for a decision algorithm and
that the elements of the decomposition can be processed independently.
Further, by equipping the components of the decomposition with suitable data structures and by carefully
splitting the problem into simpler subproblems, we make our algorithm run in linear time.
Finally, we consider several generalizations of the problem, such as minimizing the number of edges of
the partial embedding that need to be rerouted to extend it, and argue that they are NP-hard. We also apply
our algorithm to the simultaneous graph drawing problem SIMULTANEOUS EMBEDDING WITH FIXED EDGES (SEFE).
There we obtain a linear-time algorithm for the case that one of the input graphs or the common graph has
a fixed planar embedding
On the Relationship Between Map Graphs and Clique Planar Graphs
No full textA 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
Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph
No full textAbstractIn this paper we study the time complexity of the problem Simultaneous Embedding with Fixed Edges (Sefe), that takes two planar graphs G1=(V,E1) and G2=(V,E2) as input and asks whether a planar drawing Γ1 of G1 and a planar drawing Γ2 of G2 exist such that: (i) each vertex v∈V is mapped to the same point in Γ1 and in Γ2; (ii) every edge e∈E1∩E2 is mapped to the same Jordan curve in Γ1 and Γ2.First, we give a linear-time algorithm for Sefe when the intersection graph of G1 and G2, that is the planar graph G1∩2=(V,E1∩E2), is biconnected. Second, we show that Sefe, when G1∩2 is connected, is equivalent to a suitably-defined book embedding problem. Based on this equivalence and on recent results by Hong and Nagamochi, we show a linear-time algorithm for the Sefe problem when G1∩2 is a star
Graph Drawing Contest Report
Full text linkThis report describes the 28th Annual Graph Drawing Contest, held in conjunction with the 29th International Symposium on Graph Drawing and Network Visualization (GD’21) in Tübingen, Germany. Due to the global COVID-19 pandemic, the conference and thus also the contest was held in a hybrid format, with both on-site and online participants. The mission of the Graph Drawing Contest is to monitor and challenge the current state of the art in graph-drawing technology.</p
Embedding Ray Intersection Graphs and Global Curve Simplification
No full textWe prove that circle graphs (intersection graphs of circle chords) can be embedded as intersection graphs of rays in the plane with polynomial-size bit complexity. We use this embedding to show that the global curve simplification problem for the directed Hausdorff distance is NP-hard. In this problem, we are given a polygonal curve P and the goal is to find a second polygonal curve P′ such that the directed Hausdorff distance from P′ to P is at most a given constant, and the complexity of P′ is as small as possible.</p
- …
