Drawing Colored Graphs with Contrained Vertex Positions and Few Bends per Edge

Di Giacomo, Emilio and Liotta, Giuseppe and Trotta, Francesco (2008) Drawing Colored Graphs with Contrained Vertex Positions and Few Bends per Edge. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 315-326 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_31).

Full text not available from this repository.

Abstract

Hamiltonicity, book embeddability, and point-set embeddability of planar graphs are strictly related concepts. We exploit the interplay between these notions to describe colored sets of points and to design polynomial-time algorithms to embed $k$-colored planar graphs on these sets such that the resulting drawings have $O(k)$ bends per edge.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-77537-9_31
Classifications:P Styles > P.999 Others
G Algorithms and Complexity > G.210 Bends
ID Code:848

Repository Staff Only: item control page

References

M. Badent, E. Di Giacomo, and G. Liotta. Drawing colored graphs on colored points. In Proc. of 10th Work on Alg. and Data Struc. (WADS 2007). to appear.

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.

E. Di Giacomo, W. Didimo, G. Liotta, H. Meijer, F. Trotta, and S. K. Wismath. k-colored point-set embeddability of outerplanar graphs. In Graph Drawing (Proc. GD 2006), volume 4372 of LNCS, pages 318-329. Springer-Verlag, 2007.

E. Di Giacomo, W. Didimo, G. Liotta, and S. K. Wismath. Curve-constrainded drawings of planar graphs. Computational Geometry, 30:1-23, 2005.

E. Di Giacomo, G. Liotta, and F. trotta. On embedding a graph on two sets of points. IJFCS, Special issue on Graph Drawing, 17(5):1071-1094, 2006.

A. Kaneko and M. Kano. Discrete & Computational Geometry, volume 25 of Algorithms and Combinatories, pages 551-570. Springer, 2003.

M. Kaufmann and D. Wagner, editors. Drawing Graphs, volume 2025 of Lecture Notes in Computer Science. Springer-Verlag, 2001.

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.

J. Pach and R. Wenger. Embedding planar graphs at fixed vertex locations. Graph and Combinatorics, 17:717-728, 2001.