Graph Morphing via Orthogonal Box Drawings
Abstract
Abstract: A graph is a set of vertices, with some pairwise connections given by a set of edges. A graph drawing, such as a node-link diagram, visualizes a graph with geometric features. One of the most common forms of a graph drawings are straight-line point drawings, which represent each vertex with a point and each edge with a line segment connecting its relevant points, and poly-line point drawings, which more generally allow edges to be represented by poly-lines. Of particular interest to this work are planar straight-line drawings and planar poly-line drawings, in which no two vertices share a location, and no two edges cross (except at shared endpoints).
We study the morphing problem for planar drawings: Given two planar drawings of the same graph, can we output a continuous transformation (a “morph”) from one to the other, such that each intermediate drawing is also a planar drawing? It is quite easy to test if a morph exists, but the test is non-constructive. We are interested in the problem of constructing morphs with simple representations. Specifically, we study sequences of linear morphs, which represent the overall morph with a sequence of drawings, so that each pair of adjacent drawings in the sequence can be linearly interpolated. Each drawing in the sequence is called an “explicit” intermediate drawing, since it given explicitly in the output.
Previous work has shown that a pair of straight-line drawings of an n-vertex graph can be morphed using O(n) linear morphs, so that every explicit intermediate drawing is a straight-line drawing. We show that an additional constraint can be added, at the cost of a small tradeoff: We further restrict the explicit intermediate drawings to lie on an O(n)×O(n) grid, while allowing them to be poly-line drawings with O(1) bends per edge. Additionally, we give an algorithm that computes this sequence in O(n^2) time, which is known to be tight. Our methods involve morphing another class of drawings—orthogonal box drawings—which represent each vertex with an axis-aligned rectangle, and each edge with an orthogonal poly-line. Our methods for morphing orthogonal box drawings make use of methods known for morphing orthogonal point drawings, which are poly-line drawings that restrict each poly-line to use only axis-aligned line segments.
Collections
Cite this version of the work
Jack Spalding-Jamieson
(2023).
Graph Morphing via Orthogonal Box Drawings. UWSpace.
http://hdl.handle.net/10012/20172
Other formats
Related items
Showing items related by title, author, creator and subject.
-
Simultaneous Graph Representation Problems
Jampani, Krishnam Raju (University of Waterloo, 2011-02-18)Many graphs arising in practice can be represented in a concise and intuitive way that conveys their structure. For example: A planar graph can be represented in the plane with points for vertices and non-crossing curves ... -
Uniqueness and Complexity in Generalised Colouring
Farrugia, Alastair (University of Waterloo, 2003)The study and recognition of graph families (or graph properties) is an essential part of combinatorics. Graph colouring is another fundamental concept of graph theory that can be looked at, in large part, as the recognition ... -
Software Architecture Recovery based on Pattern Matching
Sartipi, Kamran (University of Waterloo, 2003)Pattern matching approaches in reverse engineering aim to incorporate domain knowledge and system documentation in the software architecture extraction process, hence provide a user/tool collaborative environment for ...