Placing axial lines in urban grids
Ian Douglas Sanders · South African Computer Journal · 2000
In earlier papers the orthogonal axial line placement problem for orthogonal rectangles and the non-orthogonal axial line placement problem in orthogonal rectangles were presented. These problems were shown to be NP-Complete by transformations from the vertex cover problem for planar graphs. the general axial line placement problem - placing axial lines to cross the adjacencies between adjacent convex polygons - is a more general case of the problem of placing non-orthogonal axial lines in orthogonal rectangles and the NP-Completeness proof can be extended to this problem as well. In this paper the axial line placement problem and the related problem of generating the convex map for polygons with holes which can be represented as urban grids are considered. the paper shows that for these arrangements of polygons the solutions can be found in polynomial time. It is also conjectured that some more general configurations could also be solved in polynomial time.