Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00158
kcolored Pointset Embeddability of Outerplanar Graphs
Emilio Di Giacomo,
Walter Didimo,
Giuseppe Liotta,
Henk Meijer,
Francesco Trotta, and
Stephen K. Wismath
Vol. 12, no. 1, pp. 2949, 2008. Regular paper.
Abstract 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},…, V_{k−1}, and k disjoint sets S_{0}, …, S_{k−1} of
points in the plane with V_{i}=S_{i} (i ∈ {0, …,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.

Submitted: December 2006.
Revised: October 2007.
