We investigate the problem of constructing planar drawings with few bends for two related problems, the partially embedded graph problem---to extend a straight-line planar drawing of a subgraph to a planar drawing of the whole graph---and the simultaneous planarity problem---to find planar drawings of two graphs that coincide on shared vertices and edges. In both cases we show that if the required planar drawings exist, then there are planar drawings with a linear number of bends per edge and, in the case of simultaneous planarity, a constant number of crossings between every pair of edges. Our proofs provide efficient algorithms if the combinatorial embedding of the drawing is given. Our result on partially embedded graph drawing generalizes a classic result by Pach and Wenger which shows that any planar graph can be drawn with a linear number of bends per edge if the location of each vertex is fixed.
Concerning SEFE, Di Giacomo and Liotta @cite_10 and independently Kammer @cite_21 proved the following result: given two planar graphs @math and @math sharing some vertices and no edge with a total number of @math vertices, there exists an @math -time algorithm to construct a simultaneous planar drawing of @math and @math on a grid of size @math , where each edge has at most @math bends, hence there are at most @math crossings between any edge of @math and any edge of @math . This improves upon a previous result of Erten and Kobourov @cite_8 . The algorithms in @cite_10 @cite_8 @cite_21 make use of a drawing technique introduced by Kaufmann and Wiese @cite_17 .
@cite_21 @cite_10 @cite_17 @cite_8
81810990 2063120809 2065527713 2055245094
Given k planar graphs G1,…,Gk, deciding whether they admit a simultaneous embedding with fixed edges (Sefe ) and whether they admit a simultaneous geometric embedding (Sge ) are NP-hard problems, for k≥3 and for k≥2, respectively. In this paper we consider the complexity of Sefe and of Sge when the graphs G1,…,Gk have a fixed planar embedding. In sharp contrast with the NP-hardness of Sefe for three non-embedded graphs, we show that Sefe is polynomial-time solvable for three graphs with a fixed planar embedding. Furthermore, we show that, given k embedded planar graphs G1,…,Gk, deciding whether a Sefe of G1,…,Gk exists and deciding whether an Sge of G1,…,Gk exists are NP-hard problems, for k≥14 and k≥13, respectively. Let G be a planar graph with n vertices and with a partition of the vertex set into subsets V"0,...,V"k"-"1 for some positive integer [email protected][email protected]?n. Let S be a set of n distinct points in the plane with a partition into subsets S"0,...,S"k"-"1 with |V"i|=|S"i| ([email protected][email protected]?k-1). This paper studies the problem of computing a planar polyline drawing of G, such that each vertex of V"i is mapped to a distinct point of S"i. Lower and upper bounds on the number of bends per edge are proved for any [email protected][email protected]?n. In the special case k=n, we improve the upper and lower bounds presented in a paper by Pach and Wenger [J. Pach, R. Wenger, Embedding planar graphs at fixed vertex locations, Graphs and Combinatorics 17 (2001) 717-728]. The upper bound is based on an algorithm for computing a topological book embedding of a planar graph, such that the vertices follow a given left-to-right order and the number of crossings between every edge and the spine is asymptotically optimal, which can be regarded as a result of independent interest. We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits. Specifically, a graph with property @math is called a @math -graph . If @math satisfies certain properties, then an n-node m-edge @math -graph G can be encoded by a binary string X such that (1) G and X can be obtained from each other in O(n log n) time, and (2) X has at most @math bits for any continuous superadditive function @math so that there are at most @math distinct @math -node @math -graphs. The methodology is applicable to general classes of graphs; this paper focuses on planar graphs. Examples of such @math include all conjunctions over the following groups of properties: (1) G is a planar graph or a plane graph; (2) @math is directed or undirected; (3) @math is triangulated, triconnected, biconnected, merely connected, or not required to be connected; (4) the nodes of G are labeled with labels from @math for @math ; (5) the edges of G are labeled with labels from @math for @math ; and (6) each node (respectively, edge) of G has at most @math self-loops (respectively, @math multiple edges). Moreover, @math and @math are not required to be O(1) for the cases of @math being a plane triangulation. These examples are novel applications of small cycle separators of planar graphs and are the only nontrivial classes of graphs, other than rooted trees, with known polynomial-time information-theoretically optimal coding schemes. In this paper we introduce a new simple strategy into edge-searching of a graph, which is useful to the various subgraph listing problems. Applying the strategy, we obtain the following four algorithms. The first one lists all the triangles in a graph G in @math time, where m is the number of edges of G and @math the arboricity of G. The second finds all the quadrangles in @math time. Since @math is at most three for a planar graph G, both run in linear time for a planar graph. The third lists all the complete subgraphs @math of order l in @math time. The fourth lists all the cliques in @math time per clique. All the algorithms require linear space. We also establish an upper bound on @math for a graph @math , where n is the number of vertices in G.