Computing Radial Drawings on the Minimum Number of Circles

Di Giacomo, Emilio and Didimo, Walter and Liotta, Giuseppe and Meijer, Henk (2004) Computing Radial Drawings on the Minimum Number of Circles. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 251-261 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_26).

Full text not available from this repository.

Abstract

A radial drawing is a representation of a graph in which the vertices lie on concentric circles of finite radius. In this paper we study the problem of computing radial drawings of planar graphs by using the minimum number of concentric circles. We assume that the edges are drawn as straight-line segments and that co-circular vertices can be adjacent. It is proven that the problem can be solved in polynomial time. Research supported in part by ldquoProgetto ALINWEB: Algoritmica per Internet e per il Webrdquo, MIUR Programmi di Ricerca Scientifica di Rilevante Interesse Nazionale, and by NSERC.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_26
Classifications:P Styles > P.720 Straight-line
P Styles > P.540 Planar
P Styles > P.120 Circular
ID Code:592

Repository Staff Only: item control page

References

C. Bachmeier, F. Brandenburg, and M. Forster. Radial level planarity testing and embedding in linear time. In Proc. GD'03, volume 2912 of LNCS, pages 393-405, 2003.

C. Bachmaier, F. Brandenburg, and M. Forster. Track planarity testing and embedding. In Proc. SOFSEM'04, volume 2, pages 3-17, 2004.

D. Bienstock and C. L. Monma. On the complexity of embedding planar graphs to minimize certain distance measures. Algorithmica, 5(1):93-109, 1990.

S. Bornholdt and H. Schuster, editors. Handbook of Graphs and Networks: From the Genome to the Internet. Wiley-VCH, 2003.

S. Cornelsen, T. Schank, and D. Wagner. Drawing graphs on two and three lines. In Proc. GD'02, volume 2528 of LNCS, pages 31-41, 2002.

E. Di Giacomo and W. Didimo. Straight-line drawings of 2-outerplanar graphs on two curves. In Proc. GD'03, volume 2912 of LNCS, pages 419-424, 2003.

E. Di Giacomo, W. Didimo, G. Liotta, and S. K. Wismath. Curve-constrained drawings of planar graphs. Comp. Geometry: Theory and Appl. to appear.

M. Dodge and R. Kitchin. Atlas of Cyberspace. Addison Wesley, 2001.

S. N. Dorogstev and J. F. F. Mendes. Evolution of Networks, From Biological Nets to the Internet and WWW. Oxford University Press, 2003.

F. Harary. Graph Theory. Addison-Wesley, 1972.

F. Harary and G. Prins. The block-cutpoint-tree of a Graph. Publ. Math Debrecen, 13:103-107, 1966.

M. Jünger and P. Mutzel, editors. Graph Drawing Software. Springer-Verlag, 2003.

K. Sugiyama. Graph DRawing and Applications for Software and Knowledge Engineers. World Scientific, 2002.