Fixed-Location Circular-Arc Drawing of Planar Graphs

Efrat, Alon and Erten, Cesim and Kobourov, Stephen G. (2004) Fixed-Location Circular-Arc Drawing of Planar Graphs. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003, Perugia, Italy , pp. 147-158 (Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_14).

Full text not available from this repository.

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 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 NP-Hard. Moreover, we show that two optimization versions of the problem are also NP-Hard. This work was partially supported by the NSF under grant ACR-02229290.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-24595-7_14
Classifications:G Algorithms and Complexity > G.420 Crossings
M Methods > M.600 Planar
P Styles > P.120 Circular
G Algorithms and Complexity > G.999 Others
ID Code:441

Repository Staff Only: item control page

References

Agarwal. Range searching. In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, CRC Press, 1997. 1997.

P. Agarwal and J. Erickson. Geometric range searching and its relatives. Advances in Discrete and Computational Geometry, 23:1-56, 1999.

P. Agarwal, M. van Kreveld, and S. Suri. Label placement by maximum independent set in rectangles. Computational Geometry: Theory and Applications, 11:209-218, 1998.

B. Apswall, M. Plass, and R. Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf. Proc. Letters, 8:121-123, 1979.

C. C. Cheng, C. A. Duncan, M. T. Goodrich, and S. G. Kobourov. Drawing planar graphs with circular arcs. Discrete and Computational Geometry, 25:405-418, 2001.

S. Doddi, M. Marathe, A. Mirzaian, B. Moret, and B. Zhu. Map labeling and its generalizations. In 8th Symposium on Discrete Algorithms, pages 148-157, 1997.

S. Doddi, M. Marathe, B. Moret. Point set labeling with specified positions. In Proc. 16th ACM Sympos. Comput. Geom. (SoCG '00), pages 182-190,2000.

A. Efrat, C. Erten, and S. G. Kobourov. Fixed-location circular-arc drawing of planar graphs. Technical Report TR03-10, Department of Computer Science, University of Arizona, 2003.

A. Efrat, A. Itai, and M. J. Katz. Geometry helps in bottleneck matching and related problems. Algorithmica, 31:1-28, 2001.

S. Even, A. Itai, and A. Shamir. On the complexity of timetable and multicommodity flow problems. SIAM J. Comput., 5:691-703, 1976.

M. Formann and F. Wagner. A packing problem with applications to lettering of maps. In Proc. 7th Annu. ACM Sympos. Comput. Geom., pages 281-288,1991.

M. Godau. On the difficulty of embedding planar graphs with inaccuracies. In Proceedings on Graph Drawing (GD '94), pages 254-261, 1994.

P. Gupta, R. Janardan, and M. Smid. Algorithms for some intersection searching problems involving circular objects. Intl. J. of Math. Algorithms, 1:35-52, 1999.

H. Imai and T. Asano. Efficient algorithms for geometric graph search problems. SIAM J. Comput., 15:478-494, 1986.

M. Kaufmann and R, Wiese. Embedding vertices at points: Few bends suffice for planar graphs. Journal of Graph Algorithms and Applications, 6(1):115-129, 2002.

D. Lichtenstein. Planar formulae and their uses. SIAM J. Comput., 11:329-343, 1982.

J. Matousek. Efficient partition trees. Discrete Comput. Geom., 8:315-334, 1992.

J. Matousek. Geometric range searching. ACM Computing Surveys, 26:421-462, 1994.

J. Pach and R. Wenger. Embedding planar graphs at fixed vertex locations. In Graph Drawing, pages 263-274, 1998.

C. Poon, B. Zhu, and F. Chin. A polynomial time solution for labeling a rectilinear map. Information Processing Letters, 65(4):201-207, 1998.

T. Strijk and M. van Kreveld. Labeling a rectilinear map more efficiently. Information Processing Letters, 69(1):25-30, 1999.

R. Tamassia and I. G. Tollis. Planar grid embedding in linear time. IEEE Trans. Circuits Syst., CAS-36(9):1230-1234, 1989.

M. van Kreveld, T. Strijk, and A. Wolff. Point set labeling with sliding labels. In Proc. 14th Annu. ACM Sympos. Comput. Geom. (SoCG'98), pages 337-346, 1998.