Search

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: The visualization of clustered graphs is a classical algorithmic topic that has several practical applications and is attracting increasing research interest. In this paper we deal with the visualization of clustered trees, a problem that is somehow foundational with respect to the one of visualizing a general clustered graph. We show many, in our opinion, surprising results that put in evidence how drawing clustered trees has many sharp differences with respect to drawing “plain” trees. We study a wide class of drawing standards, giving both negative and positive results. Namely, we show that there are clustered trees that do not have any drawing in certain standards and others that require exponential area. On the contrary, for many drawing conventions there are efficient algorithms that allow to draw clustered trees with polynomial asymptotically-optimal area. [Copyright &y& Elsevier]

Abstract: This paper studies weak proximity drawings of graphs and demonstrates their advantages over strong proximity drawings in certain cases. Weak proximity drawings are straight line drawings such that if the proximity region of two points p and q representing vertices is devoid of other points representing vertices, then segment is allowed, but not forced, to appear in the drawing. This differs from the usual, strong, notion of proximity drawing in which such segments must appear in the drawing. Most previously studied proximity regions are associated with a parameter β, . For fixed β, weak β-drawability is at least as expressive as strong β-drawability, as a strong β-drawing is also a weak one. We give examples of graph families and β values where the two notions coincide, and a situation in which it is NP-hard to determine weak β-drawability. On the other hand, we give situations where weak proximity significantly increases the expressive power of β-drawability: we show that every graph has, for all sufficiently small β, a weak β-proximity drawing that is computable in linear time, and we show that every tree has, for every β less than 2, a weak β-drawing that is computable in linear time. [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]