Covering paths and trees for planar grids

MaRDI QIDQ5177767zbMATH OpenFDO

Authors Balázs Keszegh

Publication date 5 March 2015

Full work available at URL https://arxiv.org/abs/1311.0452

zbMATH Keywords

covering pathcovering treeinteger grid

Mathematics Subject Classification ID

Combinatorial aspects of finite geometries (05B25) Combinatorial aspects of packing and covering (05B40)

Abstract: 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=mge3$, 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.

Recommendations

• Covering paths for planar point sets
• Covering paths for planar point sets
• Optimal covering of the equidistant square grid network
• Cardinality constrained path covering problems in grid graphs
• Covering the edges of a connected graph by paths

Cited in

(10)

• Covering planar graphs with forests
• Covering paths for planar point sets
• Optimal covering of the equidistant square grid network
• Covering rectangles by few monotonous polyominoes
• Cardinality constrained path covering problems in grid graphs
• Covering paths for planar point sets
• Piercing the Chessboard
• Improved bounds for covering paths and trees in the plane
• Improved bounds for covering paths and trees in the plane
• An improved bound for plane covering paths

This page was built for publication: Covering paths and trees for planar grids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5177767)