Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Fourteenth International Symposium on Graph Drawing, GD 2006
DOI: 10.7155/jgaa.00158
k-colored Point-set Embeddability of Outerplanar Graphs
Emilio Di Giacomo,
Walter Didimo,
Giuseppe Liotta,
Henk Meijer,
Francesco Trotta, and
Stephen K. Wismath
Vol. 12, no. 1, pp. 29-49, 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 V0,…, Vk−1, and k disjoint sets S0, …, Sk−1 of
points in the plane with |Vi|=|Si| (i ∈ {0, …,k−1}). The desired output is a planar drawing such that the
vertices of Vi are mapped onto the points of Si 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.
|
Journal Supporters
|