A note on the subgraphs of the (2 × ∞)-grid

Josep Díaz, Marcin Kamiński, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


We give a linear-time algorithm checking whether a graph is a subgraph of the (2 × k)-grid for some value of k. Our algorithm is based on a detailed characterization of the structure of such graphs.

Original languageEnglish (US)
Pages (from-to)531-536
Number of pages6
JournalDiscrete Mathematics
Issue number3
StatePublished - Feb 6 2010


  • Biconnected components
  • Linear-time algorithm
  • Partial grids

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'A note on the subgraphs of the (2 × ∞)-grid'. Together they form a unique fingerprint.

Cite this