Search

We 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 (n 2) 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. [ABSTRACT FROM AUTHOR]

In this paper, we show a polynomial-time algorithm for testing c -planarity of embedded flat clustered graphs with at most two vertices per cluster on each face. Our result is based on a reduction to the planar set of spanning trees in topological multigraphs (pssttm) problem, which is defined as follows. Given a (non-planar) topological multigraph A with k connected components A 1 , ... , A k , do spanning trees of A 1 , ... , A k exist such that no two edges in any two spanning trees cross? Kratochvíl et al. [SIAM Journal on Discrete Mathematics, 4(2): 223–244, 1991] proved that the problem is NP-hard even if k = 1 ; on the other hand, Di Battista and Frati presented a linear-time algorithm to solve the pssttm problem for the case in which A is a 1 -planar topological multigraph [Journal of Graph Algorithms and Applications, 13(3): 349–378, 2009]. For any embedded flat clustered graph C , an instance A of the pssttm problem can be constructed in polynomial time such that C is c -planar if and only if A admits a solution. We show that, if C has at most two vertices per cluster on each face, then it can be tested in polynomial time whether the corresponding instance A of the pssttm problem is positive or negative. Our strategy for solving the pssttm problem on A is to repeatedly perform a sequence of tests, which might let us conclude that A is a negative instance, and simplifications, which might let us simplify A by removing or contracting some edges. Most of these tests and simplifications are performed "locally", by looking at the crossings involving a single edge or face of a connected component A i of A ; however, some tests and simplifications have to consider certain global structures in A , which we call α -donuts. If no test concludes that A is a negative instance of the pssttm problem, then the simplifications eventually transform A into an equivalent 1 -planar topological multigraph on which we can apply the cited linear-time algorithm by Di Battista and Frati. [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: 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 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. [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]

A simple topological graph is k -quasiplanar (k ≥ 2) if it contains no k pairwise crossing edges, and k -planar if no edge is crossed more than k times. In this paper, we explore the relationship between k -planarity and k -quasiplanarity to show that, for k ≥ 2 , every k -planar simple topological graph can be transformed into a (k + 1) -quasiplanar simple topological graph. [ABSTRACT FROM AUTHOR]