
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.
angular resolution, Graph algorithms (graph-theoretic aspects), Graph representations (geometric and intersection representations, etc.), circular arcs, drawing planar graphs, Planar graphs; geometric and topological aspects of graph theory
angular resolution, Graph algorithms (graph-theoretic aspects), Graph representations (geometric and intersection representations, etc.), circular arcs, drawing planar graphs, Planar graphs; geometric and topological aspects of graph theory
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 41 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
