2013/11/03 by Balázs Keszegh, Keszegh, Balázs · 2 citations
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1311.0452
openalex publication_date 2013/11/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a set of points in the plane, a covering path is a polygonal path that visits all the points. In this paper we consider covering paths of the vertices of an n x m grid. We show that the minimal number of segments of such a path is 2min(n,m)-1 except when we allow crossings and n=m≥ 3, in which case the minimal number of segments of such a path is 2min(n,m)-2, i.e., in this case we can save one segment. In fact we show that these are true even if we consider covering trees instead of paths. These results extend previous works on axis-aligned covering paths of n x m grids and complement the recent study of covering paths for points in general position, in which case the problem becomes significantly harder and is still open.