Processing math: 100%
14
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Morphing Planar Graph Drawings via Orthogonal Box Drawings

      Preprint
      , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          We give an algorithm to morph planar graph drawings that achieves small grid size at the expense of allowing a constant number of bends on each edge. The input is an n-vertex planar graph and two planar straight-line drawings of the graph on an O(n)×O(n) grid. The planarity-preserving morph is composed of O(n) linear morphs between successive pairs of drawings, each on an O(n)×O(n) grid with a constant number of bends per edge. The algorithm to compute the morph runs in O(n2) time on a word RAM model with standard arithmetic operations -- in particular no square roots or cube roots are required. The first step of the algorithm is to morph each input drawing to a planar orthogonal box drawing where vertices are represented by boxes and each edge is drawn as a horizontal or vertical segment. The second step is to morph between planar orthogonal box drawings. This is done by extending known techniques for morphing planar orthogonal drawings with point vertices.

          Related collections

          Author and article information

          Journal
          06 September 2024
          Article
          2409.04074
          2e8ae001-a155-4bb4-82bb-66b5fec9e4c4

          http://creativecommons.org/licenses/by/4.0/

          History
          Custom metadata
          To appear in the proceedings of the 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)
          cs.CG

          Theoretical computer science
          Theoretical computer science

          Comments

          Comment on this article