n South African Computer Journal - Placing axial lines in urban grids

Volume 2000, Issue 26
  • ISSN : 1015-7999
  • E-ISSN: 2313-7835



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.

Loading full text...

Full text loading...


Article metrics loading...


This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error