FixedLocation CircularArc Drawing of Planar GraphsEfrat, Alon and Erten, Cesim and Kobourov, Stephen G. (2004) FixedLocation CircularArc Drawing of Planar Graphs. In: Graph Drawing 11th International Symposium, GD 2003, September 2124, 2003 , pp. 147158(Official URL: http://dx.doi.org/10.1007/9783540245957_14). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783540245957_14
AbstractIn this paper we consider the problem of drawing a planar graph using circulararcs as edges, given a onetoone mapping between the vertices of the graph and a set of n points on the plane, where n is the number of vertices in the graph. If for every edge we have only two possible circular arcs, then a simple reduction to 2SAT yields an O(n^2) algorithm to find out if a drawing with no crossings can be realized. We present an improved O(n^{7/4} polylog n) time algorithm. For the special case where the possible circular arcs for each edge are of the same length, we present an even more efficient algorithm that runs in O(n^{3/2} polylog n) time. We also consider the problem if we have more than two possible circular arcs per edge and show that the problem becomes NPHard. Moreover, we show that two optimization versions of the problem are also NPHard. This work was partially supported by the NSF under grant ACR02229290.
Actions (login required)
