Abstract
Orthogonal drawings, i.e., embeddings of graphs into grids, are a classic topic in Graph Drawing. Often the goal is to find a drawing that minimizes the number of bends on the edges. A key ingredient for bend minimization algorithms is the existence of an orthogonal representation that allows to describe such drawings purely combinatorially by only listing the angles between the edges around each vertex and the directions of bends on the edges, but neglecting any kind of geometric information such as vertex coordinates or edge lengths.
Barth et al. [2017] have established the existence of an analogous orthoradial representation for orthoradial drawings, which are embeddings into an orthoradial grid, whose gridlines are concentric circles around the origin and straightline spokes emanating from the origin but excluding the origin itself. While any orthogonal representation admits an orthogonal drawing, it is the circularity of the orthoradial grid that makes the problem of characterizing valid orthoradial representations all the more complex and interesting. Barth et al. prove such a characterization. However, the proof is existential and does not provide an efficient algorithm for testing whether a given orthoradial representation is valid, let alone actually obtaining a drawing from an orthoradial representation.
In this paper we give quadratictime algorithms for both of these tasks. They are based on a suitably constrained leftfirst DFS in planar graphs and several new insights on orthoradial representations. Our validity check requires quadratic time, and a naive application of it would yield a quartic algorithm for constructing a drawing from a valid orthoradial representation. Using further structural insights we speed up the drawing algorithm to quadratic running time.
BibTeX  Entry
@InProceedings{niedermann_et_al:LIPIcs:2019:10457,
author = {Benjamin Niedermann and Ignaz Rutter and Matthias Wolf},
title = {{Efficient Algorithms for OrthoRadial Graph Drawing}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {53:153:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771047},
ISSN = {18688969},
year = {2019},
volume = {129},
editor = {Gill Barequet and Yusu Wang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10457},
URN = {urn:nbn:de:0030drops104572},
doi = {10.4230/LIPIcs.SoCG.2019.53},
annote = {Keywords: Graph Drawing, OrthoRadial Graph Drawing, OrthoRadial Representation, TopologyShapeMetrics, Efficient Algorithms}
}
Keywords: 

Graph Drawing, OrthoRadial Graph Drawing, OrthoRadial Representation, TopologyShapeMetrics, Efficient Algorithms 
Collection: 

35th International Symposium on Computational Geometry (SoCG 2019) 
Issue Date: 

2019 
Date of publication: 

11.06.2019 