Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00367
Fitting Planar Graphs on Planar Maps
Vol. 19, no. 1, pp. 413-440, 2015. Regular paper.
Abstract Graph and cartographic visualization have the common objective to provide
intuitive understanding of some underlying data. We consider a problem
that combines aspects of both by studying the problem of fitting planar
graphs on planar maps.
After providing an NP-hardness result for the general decision problem,
we identify sufficient conditions so that a fit is possible on a map with rectangular regions.
We generalize our techniques to non-convex rectilinear polygons, where we also address
the problem of efficient distribution of the vertices inside the map regions.
|
Submitted: November 2013.
Reviewed: May 2014.
Revised: October 2014.
Accepted: November 2014.
Final: August 2015.
Published: September 2015.
Communicated by
Henk Meijer
|
Journal Supporters
|