k-colored point-set embeddability of outerplanar graphs

Wismath, Stephen K. and Di Giacomo, Emilio and Didimo, Walter and Liotta, Giuseppe and Meijer, Henk and Trotta, Francesco (2007) k-colored point-set embeddability of outerplanar graphs. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 318-329 (Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_31).

Full text not available from this repository.


This paper addresses the problem of designing drawing algorithms that receive as input a planar graph G, a partitioning of the vertices of G into k different semantic categories V_0,\cdots, V_{k-1}, and k disjoint sets S_0, \cdots, S_{k-1} of points in the plane with |V_i|=|S_i| (i \in \{0, \cdots, k-1\}).The desired output is a planar drawing such that the vertices of V_i are mapped onto the points of S_i and such that the curve complexity of the edges (i.e. the number of bends along each edge) is kept small. Particular attention is devoted to outerplanar graphs, for which lower and upper bounds on the number of bends in the drawings are established.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_31
Classifications:M Methods > M.600 Planar
P Styles > P.540 Planar
G Algorithms and Complexity > G.210 Bends
ID Code:786

Repository Staff Only: item control page


P. Bose. On embedding an outer-planar graph on a point set. Computational Geometry: Theory and Applications, 23:303-312, 2002.P. Bose, M. McAllister, and J. Snoeyink. Optimal algorithms to embed trees in a point set. Journal of Graph Algorithms and Applications, 2(1):1-15, 1997.

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. Technical Report RT-002-06, Dip. di Ingegneria Elettronica e dell'Informazione, Univ. of Perugia, 2006.

E. Di Giacomo, G. Liotta, and F. Trotta. On embedding a graph on two sets of points. IJFCS, Special Issue on Graph Drawing 2005. to appear.

E. Di Giacomo, G. Liotta, and F. Trotta. How to embed a path onto two sets of points. In Proc. GD 2005, volume 3843 of LNCS, pages 111-116. Springer, 2005.

P. Gritzmann, B. Mohar, J. Pach, and R. Pollack. Embedding a planar triangulation with vertices at specied points. Am. Math. Month., 98(2):165-166, 1991.

J. H. Halton. On the thickness of graphs of given degree. Information Sciences, 54:219-238, 1991.

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 suce for planar graphs. Journal of Graph Algorithms and Applications, 6(1):115-129, 2002.

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

K. Sugiyama. Graph Drawing and Applications for Software and Knowledge Engineers. Word Scientic, 2002.

R. Tamassia, G. Di Battista, and C. Batini. Automatic graph drawing and readability of diagrams. IEEE Trans. Sys., Man, and Cyber., SMC-18(1):61-79, 1988.