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
article (PDF)