Search

We 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. [ABSTRACT FROM AUTHOR]

We prove that planar graphs have O(log² n) queue number, thus improving upon the previous O(√n) upper bound. Consequently, planar graphs admit three-dimensional straight-line crossing-free grid drawings in O(n log8 n) volume, thus improving upon the previous O(n3/2) upper bound. [ABSTRACT FROM AUTHOR]

We show that every plane graph admits a planar straight-line drawing in which all faces with more than three vertices are nonconvex polygons. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we study the time complexity of the problem Simultaneous Embedding with Fixed Edges (Sefe), that takes two planar graphs and as input and asks whether a planar drawing of and a planar drawing of exist such that: (i) each vertex is mapped to the same point in and in ; (ii) every edge is mapped to the same Jordan curve in and . First, we give a linear-time algorithm for Sefe when the intersection graph of and , that is the planar graph , is biconnected. Second, we show that Sefe, when 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 is a star. [Copyright &y& Elsevier]

Abstract: Consider a planar drawing of a planar graph such that the vertices are drawn as small circles and the edges are drawn as thin stripes. Consider a non-simple cycle of . Is it possible to draw as a non-intersecting closed curve inside , following the circles that correspond in to the vertices of and the stripes that connect them? We show that this test can be done in polynomial time and study this problem in the framework of clustered planarity for highly non-connected clustered graphs. [Copyright &y& Elsevier]

In this paper we consider the important class of directed acyclic graphs (DAGs), and present the results of a comparative study on four popular drawing algorithms specifically developed for them. The study has been performed within a general experimental setting consisting of two large test suites of DAGs and a set of quality measures. The focus of the experiments has been the practical behavior of the algorithms with a geometric foundation compared to that of the algorithms with a topological foundation. The four algorithms exhibit various trade-offs with respect to the quality measures considered, and none of them clearly outperforms the others. Our analysis has motivated the development of a new hybrid strategy for drawing DAGs that performs quite well in practice. [ABSTRACT FROM AUTHOR]

A diagram is a drawing on the plane that represents a graph-like structure, where nodes are represented by symbols and edges are represented by curves connecting pairs of symbols. An automatic layout facility is a tool that receives as input a graph-like structure and is able to produce a diagram that nicely represents such a structure. Many systems use diagrams in the interaction with the users; thus, automatic layout facilities and algorithms for graphs layout have been extensively studied in the last years. We present a new approach in designing an automatic layout facility. Our approach is based on a modular management of a large collection of algorithms and on a strategy that, given the requirements of an application, selects a suitable algorithm for such requirements. The proposed approach has been used for designing the automatic layout facility of Diagram Server, a network server that offers to its clients several facilities for managing diagrams. [ABSTRACT FROM AUTHOR]

In a drawing of a clustered graph vertices and edges are drawn as points and curves, respectively, while clusters are represented by simple closed regions. A drawing of a clustered graph is c-planar if it has no edge–edge, edge–region, or region–region crossings. Determining the complexity of testing whether a clustered graph admits a c-planar drawing is a long-standing open problem in the Graph Drawing research area. An obvious necessary condition for c-planarity is the planarity of the graph underlying the clustered graph. However, this condition is not sufficient and the consequences on the problem due to the requirement of not having edge–region and region–region crossings are not yet fully understood. In order to shed light on the c-planarity problem, we consider a relaxed version of it, where some kinds of crossings (either edge–edge, edge–region, or region–region) are allowed even if the underlying graph is planar. We investigate the relationships among the minimum number of edge–edge, edge–region, and region–region crossings for drawings of the same clustered graph. Also, we consider drawings in which only crossings of one kind are admitted. In this setting, we prove that drawings with only edge–edge or with only edge–region crossings always exist, while drawings with only region–region crossings may not. Further, we provide upper and lower bounds for the number of such crossings. Finally, we give a polynomial-time algorithm to test whether a drawing with only region–region crossings exists for biconnected graphs, hence identifying a first non-trivial necessary condition for c-planarity that can be tested in polynomial time for a noticeable class of graphs. [ABSTRACT FROM AUTHOR]