Minimum length corridor problem on grids

Jahanbekam, Sogol; Ramu, Sindhu; Sohrabi, Elham

doi:10.2140/involve.2025.18.665

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

This article is available for purchase or by subscription. See below.

Minimum length corridor problem on grids

Sogol Jahanbekam, Sindhu Ramu and Elham Sohrabi

Vol. 18 (2025), No. 4, 665–682

DOI: 10.2140/involve.2025.18.665

Abstract

Let $B$ be a rectangle that is decomposed into subrectangles. A corridor of $B$ is a tree $T$ whose edges belong to $B$ , where $T$ has a vertex in the outer boundary and in each of the subrectangles in $B$ . A minimum-length corridor (MLC) is a corridor with the smallest length sum over its edges. In this paper, we determine the minimum-length corridor of the rectangles that are subdivided by horizontal and vertical lines into smaller rectangles (grids) when all horizontal (or vertical) line segments have the same length $k$ and the rest of the line segments have a length of at least $k$ . We also determine an upper bound for the minimum-length corridor of the grids when all horizontal (or vertical) line segments have the same length $k$ and the rest of line segments have length at most $k$ . We conclude with a conjecture that the upper bound is tight for some cases.

PDF Access Denied

We have not been able to recognize your IP address 18.97.14.89 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recommendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 30.00:

Keywords

trees, geometric aspects of graph theory, applications of graph theory, tiling

Mathematical Subject Classification

Primary: 05B45, 05C05, 05C09, 05C90

Milestones

Received: 7 September 2023

Revised: 28 February 2024

Accepted: 6 March 2024

Published: 30 July 2025

Communicated by Joshua Cooper

Authors

Sogol Jahanbekam
Department of Mathematics and Statistics San Jose State University San Jose, CA United States

Sindhu Ramu
Department of Mathematics and Statistics San Jose State University San Jose, CA United States

Elham Sohrabi
Division of Mathematics and Computer Science University of South Carolina Upstate Spartanburg, SC United States

Vol. 18, No. 4, 2025