Drawing planar graphs with circular arcs

DOI10.1007/S004540010080MaRDI QIDQ5944937zbMATH OpenOpenAlexFDO

Authors C. C. Cheng, Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov

Publication date 10 October 2001

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s004540010080

angular resolution circular arcs drawing planar graphs

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

The authors study the problem of drawing planar graphs with circular arcs, while maintaining good angular resolution and small drawing area. They show the following: (1) There is an \(n\)-vertex planar graph requiring area exponential in \(n\) for any drawing using single-circle arcs for edges and having good angular resolution. (2) Let \(d(v)\) be the degree of vertex \(v\). An \(n\)-vertex planar graph can be drawn in an \(O(n)\times O(n)\) grid with angular resolution \(\Theta(1/d(v))\) for each vertex \(v\), using at most two circular arcs per edge. In this case circular arcs of infinite radius are used, so that the polylines are piecewise linear with at most one bend each, while maintaining good angular resolution and \(O(n)\times O(n)\) area. (3) An \(n\)-vertex planar graph can be drawn in an \(O(n)\times O(n)\) grid with angular resolution as above, using \(C^1\)-continuous curves consisting of at most three circular arcs.

Recommendations

Cites work

Cited in

(18)

This page was built for publication: Drawing planar graphs with circular arcs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5944937)