Fixed-Location Circular-Arc Drawing of Planar Graphs

In this paper we consider the problem of drawing a planar graph using circular-arcs as edges, given a one-to-one 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(n2) algorithm to find out if a drawing with no crossings can be realized. We present an improved O(n7/4polylogn) 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(n3/2polylogn) time. We also consider the problem if we have more than two possible circular arcs per edge and show that the problem becomes NP-Hard. Moreover, we show that two optimization versions of the problem are also NP-Hard.