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 , 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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/786

Actions (login required)

View Item View Item