Drawing planar graphs with circular arcs (Q5944937)

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.