Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00140
Fixed-Location Circular Arc Drawing of Planar Graphs
Vol. 11, no. 1, pp. 145-164, 2007. Regular paper.
Abstract 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 points in the plane.
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, where n is the number of
vertices in the graph. We present an improved O(n7/4polylog n)
time algorithm for this problem. 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/2polylog n) time. We also
consider two related optimization versions of the problem. First we show that
minimizing the number of crossings is NP-hard. Second
we show that
maximizing the number of edges that can be realized without crossings
is also NP-hard. Finally, we show that if we have three or more
possible circular arcs per edge, deciding whether a drawing with no
crossings can be realized is NP-hard.
|
Journal Supporters
|