×

A note on the subgraphs of the (\(2\times \infty \))-grid. (English) Zbl 1216.05157

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

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Caprara, A.; Malucelli, F.; Pretolani, D., On bandwidth-2 graphs, Discrete Applied Mathematics. The Journal of Combinatorial Algorithms, Informatics and Computational Sciences, 117, 1-3, 1-13 (2002) · Zbl 0994.05130
[2] Garey, M. R.; Graham, R. L.; Johnson, D. S.; Knuth, D. E., Complexity results for bandwidth minimization, SIAM Journal on Applied Mathematics, 34, 3, 477-495 (1978) · Zbl 0385.05048
[3] Gurari, E. M.; Sudborough, I. H., Improved dynamic programming algorithms for bandwidth minimization and the MINCUT linear arrangement problem, Journal of Algorithms, 5, 4, 531-546 (1984) · Zbl 0556.68012
[4] Matoušek, J.; Nešetřil, J., Invitation to Discrete Mathematics (1998), Oxford U.P · Zbl 0901.05001
[5] Matoušek, J.; Thomas, R., On the complexity of finding iso- and other morphisms for partial \(k\)-trees, Discrete Mathematics, 108, 343-364 (1992) · Zbl 0764.68128
[6] Yamazaki, K.; Tani, S.; Nishino, T., A characterization of \(k\)-th powers \(P_{n, k}\) of paths in terms of \(k\)-trees, International Journal of Foundations of Computer Science, 12, 4, 435-443 (2001) · Zbl 1320.05098
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.