Towards a topology-shape-metrics framework for ortho-radial drawings

L. Barth, B. Niedermann, I. Rutter, M. Wolf

Research output: Contribution to journalArticleAcademic

36 Downloads (Pure)

Abstract

Ortho-Radial drawings are a generalization of orthogonal drawings to grids that are formed by concentric circles and straight-line spokes emanating from the circles' center. Such drawings have applications in schematic graph layouts, e.g., for metro maps and destination maps. A plane graph is a planar graph with a fixed planar embedding. We give a combinatorial characterization of the plane graphs that admit a planar ortho-radial drawing without bends. Previously, such a characterization was only known for paths, cycles, and theta graphs, and in the special case of rectangular drawings for cubic graphs, where the contour of each face is required to be a rectangle. The characterization is expressed in terms of an ortho-radial representation that, similar to Tamassia's orthogonal representations for orthogonal drawings describes such a drawing combinatorially in terms of angles around vertices and bends on the edges. In this sense our characterization can be seen as a first step towards generalizing the Topology-Shape-Metrics framework of Tamassia to ortho-radial drawings.
Original languageEnglish
Article number1703.06040v1
Pages (from-to)1-35
JournalarXiv
Volume2017
Publication statusPublished - 2017

Fingerprint

Topology
Metric
Plane Graph
Circle
Graph Layout
Drawing
Framework
Cubic Graph
Concentric
Straight Line
Planar graph
Rectangle
Face
Grid
Cycle
Angle
Path
Graph in graph theory

Bibliographical note

Extended version of a paper to appear at the 33rd International Symposium on Computational Geometry (SoCG 2017)

Keywords

  • cs.DM
  • cs.DS

Cite this

Barth, L., Niedermann, B., Rutter, I., & Wolf, M. (2017). Towards a topology-shape-metrics framework for ortho-radial drawings. arXiv, 2017, 1-35. [1703.06040v1].
Barth, L. ; Niedermann, B. ; Rutter, I. ; Wolf, M. / Towards a topology-shape-metrics framework for ortho-radial drawings. In: arXiv. 2017 ; Vol. 2017. pp. 1-35.
@article{b1432d5a0613471d9be04cb04dea7242,
title = "Towards a topology-shape-metrics framework for ortho-radial drawings",
abstract = "Ortho-Radial drawings are a generalization of orthogonal drawings to grids that are formed by concentric circles and straight-line spokes emanating from the circles' center. Such drawings have applications in schematic graph layouts, e.g., for metro maps and destination maps. A plane graph is a planar graph with a fixed planar embedding. We give a combinatorial characterization of the plane graphs that admit a planar ortho-radial drawing without bends. Previously, such a characterization was only known for paths, cycles, and theta graphs, and in the special case of rectangular drawings for cubic graphs, where the contour of each face is required to be a rectangle. The characterization is expressed in terms of an ortho-radial representation that, similar to Tamassia's orthogonal representations for orthogonal drawings describes such a drawing combinatorially in terms of angles around vertices and bends on the edges. In this sense our characterization can be seen as a first step towards generalizing the Topology-Shape-Metrics framework of Tamassia to ortho-radial drawings.",
keywords = "cs.DM, cs.DS",
author = "L. Barth and B. Niedermann and I. Rutter and M. Wolf",
note = "Extended version of a paper to appear at the 33rd International Symposium on Computational Geometry (SoCG 2017)",
year = "2017",
language = "English",
volume = "2017",
pages = "1--35",
journal = "arXiv",
publisher = "Cornell University Library",

}

Barth, L, Niedermann, B, Rutter, I & Wolf, M 2017, 'Towards a topology-shape-metrics framework for ortho-radial drawings', arXiv, vol. 2017, 1703.06040v1, pp. 1-35.

Towards a topology-shape-metrics framework for ortho-radial drawings. / Barth, L.; Niedermann, B.; Rutter, I.; Wolf, M.

In: arXiv, Vol. 2017, 1703.06040v1, 2017, p. 1-35.

Research output: Contribution to journalArticleAcademic

TY - JOUR

T1 - Towards a topology-shape-metrics framework for ortho-radial drawings

AU - Barth, L.

AU - Niedermann, B.

AU - Rutter, I.

AU - Wolf, M.

N1 - Extended version of a paper to appear at the 33rd International Symposium on Computational Geometry (SoCG 2017)

PY - 2017

Y1 - 2017

N2 - Ortho-Radial drawings are a generalization of orthogonal drawings to grids that are formed by concentric circles and straight-line spokes emanating from the circles' center. Such drawings have applications in schematic graph layouts, e.g., for metro maps and destination maps. A plane graph is a planar graph with a fixed planar embedding. We give a combinatorial characterization of the plane graphs that admit a planar ortho-radial drawing without bends. Previously, such a characterization was only known for paths, cycles, and theta graphs, and in the special case of rectangular drawings for cubic graphs, where the contour of each face is required to be a rectangle. The characterization is expressed in terms of an ortho-radial representation that, similar to Tamassia's orthogonal representations for orthogonal drawings describes such a drawing combinatorially in terms of angles around vertices and bends on the edges. In this sense our characterization can be seen as a first step towards generalizing the Topology-Shape-Metrics framework of Tamassia to ortho-radial drawings.

AB - Ortho-Radial drawings are a generalization of orthogonal drawings to grids that are formed by concentric circles and straight-line spokes emanating from the circles' center. Such drawings have applications in schematic graph layouts, e.g., for metro maps and destination maps. A plane graph is a planar graph with a fixed planar embedding. We give a combinatorial characterization of the plane graphs that admit a planar ortho-radial drawing without bends. Previously, such a characterization was only known for paths, cycles, and theta graphs, and in the special case of rectangular drawings for cubic graphs, where the contour of each face is required to be a rectangle. The characterization is expressed in terms of an ortho-radial representation that, similar to Tamassia's orthogonal representations for orthogonal drawings describes such a drawing combinatorially in terms of angles around vertices and bends on the edges. In this sense our characterization can be seen as a first step towards generalizing the Topology-Shape-Metrics framework of Tamassia to ortho-radial drawings.

KW - cs.DM

KW - cs.DS

M3 - Article

VL - 2017

SP - 1

EP - 35

JO - arXiv

JF - arXiv

M1 - 1703.06040v1

ER -

Barth L, Niedermann B, Rutter I, Wolf M. Towards a topology-shape-metrics framework for ortho-radial drawings. arXiv. 2017;2017:1-35. 1703.06040v1.