Abstract A morph is a continuous transformation between two representations of a graph. We consider the problem of morphing between contact representations of a plane graph. In an $${\mathcal {F}}$$ F -contact representation of a plane graph G, vertices are realized by internally disjoint elements from a family $${\mathcal {F}}$$ F of connected geometric objects. Two such elements touch if and only if their corresponding vertices are adjacent. These touchings also induce the same embedding as in G. In a morph between two $${\mathcal {F}}$$ F -contact representations we insist that at each time step (continuously throughout the morph) we have an $${\mathcal {F}}$$ F -contact representation. We focus on the case when $$\mathcal {F}$$ F is the family of triangles in $$\mathbb {R}^2$$ R 2 that are the lower-right half of axis-parallel rectangles. Such RT-representations exist for every plane graph and right triangles are one of the simplest families of shapes supporting this property. Moreover, they naturally correspond to 3-orientations. Thus, they provide a natural case to study regarding morphs of contact representations of plane graphs. We characterize the pairs of RT-representations admitting a morph between each other via the respective 3-orientations. Our characterization leads to a polynomial-time algorithm to decide whether there is a morph between two RT-representations of an n-vertex plane triangulation, and, if so, computes a morph with $${\mathcal {O}}(n^2)$$ O ( n 2 ) steps. Each of these steps is a linear morph moving the endpoints of each triangle at constant speed along straight-line trajectories. Our characterization also implies that for 4-connected plane triangulations there is a morph between every pair of RT-representations where the “top-most” triangle in both representations corresponds to the same vertex.

We consider the problem of morphing between contact representations of a plane graph. In a contact representation of a plane graph, vertices are realized by internally disjoint elements from a family of connected geometric objects. Two such elements touch if and only if their corresponding vertices are adjacent. These touchings also induce the same embedding as in the graph. In a morph between two contact representations we insist that at each time step (continuously throughout the morph) we have a contact representation of the same type. We focus on the case when the geometric objects are triangles that are the lower-right half of axis-parallel rectangles. Such RT-representations exist for every plane graph and right triangles are one of the simplest families of shapes supporting this property. Thus, they provide a natural case to study regarding morphs of contact representations of plane graphs. We study piecewise linear morphs, where each step is a linear morph moving the endpoints of each triangle at constant speed along straight-line trajectories. We provide a polynomial-time algorithm that decides whether there is a piecewise linear morph between two RT-representations of a plane triangulation, and, if so, computes a morph with a quadratic number of linear morphs. As a direct consequence, we obtain that for 4-connected plane triangulations there is a morph between every pair of RT-representations where the "top-most" triangle in both representations corresponds to the same vertex. This shows that the realization space of such RT-representations of any 4-connected plane triangulation forms a connected set.

We study a family of algorithms, introduced by Chan [SODA 1999], for drawing ordered rooted binary trees. Any algorithm in this family (which we name an LR-algorithm) takes in input an ordered rooted binary tree T with a root rT, and recursively constructs drawings of the left subtree L of rT and of the right subtree R of rT; then either it applies the left rule, i.e., it places one unit below and to the left of rT, and one unit below with the root of R vertically aligned with rT, or it applies the right rule, i.e., it places one unit below and to the right of rT, and ΓL one unit below with the root of L vertically aligned with rT. In both cases, the edges between rT and its children are represented by straight-line segments. Different LR- algorithms result from different choices on whether the left or right rule is applied at any node of T. We are interested in constructing LR-drawings (that are drawings obtained via LR-algorithms) with small width. Chan showed three LR- algorithms that achieve, for an n-node ordered rooted binary tree, width O(n0.695), width O(n0.5), and width O(n0.48). We prove that, for every n-node ordered rooted binary tree, an LR-drawing with minimum width can be constructed in O(n1.48) time. Further, we show an infinite family of n-node ordered rooted binary trees requiring Ω(n°.418) width in any LR-drawing; no lower bound better than n(log n) was previously known. Finally, we present the results of an experimental evaluation that allowed us to determine the minimum width of all the ordered rooted binary trees with up to 455 nodes. Our interest in LR-drawings is mainly motivated by a result of Di Battista and Frati [Algorithmica 2009], who proved that n-vertex outerplanar graphs have outerplanar straight-line drawings in O(n1.48) area by means of a drawing algorithm which resembles an LR-algorithm. We deepen the connection between LR-drawings and outerplanar drawings by proving that, if n-node ordered rooted binary trees have LR-drawings with f (n) width, for any function f (n), then n-vertex outerplanar graphs have outerplanar straight-line drawings in O(f (n)) area. Finally, we exploit a structural decomposition for ordered rooted binary trees introduced by Chan in order to prove that every n-vertex outerplanar graph has an outer-planar straight-line drawing in area.

Given an $n$-vertex graph and two straight-line planar drawings of the graph that have the same faces and the same outer face, we show that there is a morph (i.e., a continuous transformation) between the two drawings that preserves straight-line planarity and consists of $O(n)$ steps, which we prove is optimal in the worst case. Each step is a unidirectional linear morph, which means that every vertex moves at constant speed along a straight line, and the lines are parallel although the vertex speeds may differ. Thus we provide an efficient version of Cairns' 1944 proof of the existence of straight-line planarity-preserving morphs for triangulated graphs, which required an exponential number of steps.

We give an algorithm to compute a morph between any two convex drawings of the same plane graph. The morph preserves the convexity of the drawing at any time instant and moves each vertex along a piecewise linear curve with linear complexity. The linear bound is asymptotically optimal in the worst case.

Bitcoin is a digital currency whose transactions are stored into a public ledger, called blockchain, that can be viewed as a directed graph with more than 70 million nodes, where each node represents a transaction and each edge represents Bitcoins flowing from one transaction to another one. We describe a system for the visual analysis of how and when a flow of Bitcoins mixes with other flows in the transaction graph. Such a system relies on high-level metaphors for the representation of the graph and the size and characteristics of transactions, allowing for high level analysis of big portions of it.

In 1944, Cairns proved the following theorem: given any two straight-line planar drawings of a triangulation with the same outer face, there exists a morph (i.e., a continuous transformation) between the two drawings so that the drawing remains straight-line planar at all times. Cairns's original proof required exponentially many morphing steps. We prove that there is a morph that consists of O(n2) steps, where each step is a linear morph that moves each vertex at constant speed along a straight line. Using a known result on compatible triangulations this implies that for a general planar graph G and any two straight-line planar drawings of G with the same embedding, there is a morph between the two drawings that preserves straight-line planarity and consists of O(n4) steps.