Search

In this paper we study planar morphs between planar straight-line grid drawings of trees. A morph consists of a sequence of morphing steps, where in a morphing step vertices move along straight-line trajectories at constant speed. We show how to construct planar morphs that simultaneously achieve a reduced number of morphing steps and a polynomially-bounded resolution. We assume that both the initial and final drawings lie on the grid and we ensure that each morphing step produces a grid drawing; further, we consider both upward drawings of rooted trees and drawings of arbitrary trees. [ABSTRACT FROM AUTHOR]

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]

A point set S⊆R2 is universal for a class G of planar graphs if every graph of G has a planar straight-line embedding on S. It is well-known that the integer grid is a quadratic-size universal point set for planar graphs, while the existence of a subquadratic universal point set still remains one of the most fascinating open problems in Graph Drawing. In this paper we make a major step towards a solution for this problem. Motivated by the fact that each point set of size n in general position is universal for the class of n-vertex outerplanar graphs, we concentrate our attention on k-outerplanar graphs. We prove that they admit an O(nlogn)-size universal point set in two distinct cases, namely when k=2 (2-outerplanar graphs) and when k is unbounded but each outerplanarity level is restricted to be a simple cycle (simply-nested graphs). [ABSTRACT FROM AUTHOR]

A graph is k-planar ]> ]> ( k ≥ 1 ) ]> if it can be drawn in the plane such that no edge is crossed ]> ]> k + 1 ]> times or more. A graph is k-quasi-planar ]> ]> ( k ≥ 2 ) ]> if it can be drawn in the plane with no k pairwise crossing edges. The families of k-planar and k-quasi-planar graphs have been widely studied in the literature, and several bounds have been proven on their edge density. Nonetheless, only trivial results are known about the relationship between these two graph families. In this paper we prove that, for ]> ]> k ≥ 3 ]> , every k-planar graph is ]> ]> ( k + 1 ) ]> -quasi-planar. [ABSTRACT FROM AUTHOR]