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

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

doi:10.1016/j.disc.2009.03.046

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

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

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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 language	English (US)
Pages (from-to)	531-536
Number of pages	6
Journal	Discrete Mathematics
Volume	310
Issue number	3
DOIs	https://doi.org/10.1016/j.disc.2009.03.046
State	Published - Feb 6 2010

Keywords

Biconnected components
Linear-time algorithm
Partial grids

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2009.03.046

Cite this

@article{084fc3be81994df2b358af8c44e68950,

title = "A note on the subgraphs of the (2 × ∞)-grid",

abstract = "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.",

keywords = "Biconnected components, Linear-time algorithm, Partial grids",

author = "Josep D{\'i}az and Marcin Kami{\'n}ski and Thilikos, {Dimitrios M.}",

year = "2010",

month = feb,

day = "6",

doi = "10.1016/j.disc.2009.03.046",

language = "English (US)",

volume = "310",

pages = "531--536",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

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

AU - Díaz, Josep

AU - Kamiński, Marcin

AU - Thilikos, Dimitrios M.

PY - 2010/2/6

Y1 - 2010/2/6

N2 - 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.

AB - 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.

KW - Biconnected components

KW - Linear-time algorithm

KW - Partial grids

UR - http://www.scopus.com/inward/record.url?scp=70449721885&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70449721885&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2009.03.046

DO - 10.1016/j.disc.2009.03.046

M3 - Article

AN - SCOPUS:70449721885

SN - 0012-365X

VL - 310

SP - 531

EP - 536

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 3

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this