Fitting Planar Graphs on Planar Maps - Alam, Md. Jawaherul; Kaufmann, Michael; Kobourov, Stephen; Mchedlidze, Tamara (Journal of Graph Algorithms and Applications, 2015)
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.