Common unfoldings of polyominoes and polycubes

Greg Aloupis; Prosenjit K. Bose; Sébastien Collette; Erik D. Demaine; Martin L. Demaine; Karim Douïeb; Vida Dujmović; John Iacono; Stefan Langerman; Pat Morin

doi:10.1007/978-3-642-24983-9_5

Common unfoldings of polyominoes and polycubes

Greg Aloupis, Prosenjit K. Bose, Sébastien Collette, Erik D. Demaine, Martin L. Demaine, Karim Douïeb, Vida Dujmović, John Iacono, Stefan Langerman, Pat Morin

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

This paper studies common unfoldings of various classes of polycubes, as well as a new type of unfolding of polyominoes. Previously, Knuth and Miller found a common unfolding of all tree-like tetracubes. By contrast, we show here that all 23 tree-like pentacubes have no such common unfolding, although 22 of them have a common unfolding. On the positive side, we show that there is an unfolding common to all "non-spiraling" k-ominoes, a result that extends to planar non-spiraling k-cubes.

Original language	English (US)
Title of host publication	Computational Geometry, Graphs and Applications - 9th International Conference, CGGA 2010, Revised Selected Papers
Pages	44-54
Number of pages	11
DOIs	https://doi.org/10.1007/978-3-642-24983-9_5
State	Published - 2011
Event	9th International Conference on Computational Geometry, Graphs and Applications, CGGA 2010 - Dalian, China Duration: Nov 3 2010 → Nov 6 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7033 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	9th International Conference on Computational Geometry, Graphs and Applications, CGGA 2010
Country/Territory	China
City	Dalian
Period	11/3/10 → 11/6/10

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-24983-9_5

Cite this

Aloupis, G., Bose, P. K., Collette, S., Demaine, E. D., Demaine, M. L., Douïeb, K., Dujmović, V., Iacono, J., Langerman, S., & Morin, P. (2011). Common unfoldings of polyominoes and polycubes. In Computational Geometry, Graphs and Applications - 9th International Conference, CGGA 2010, Revised Selected Papers (pp. 44-54). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7033 LNCS). https://doi.org/10.1007/978-3-642-24983-9_5

Common unfoldings of polyominoes and polycubes. / Aloupis, Greg; Bose, Prosenjit K.; Collette, Sébastien et al.
Computational Geometry, Graphs and Applications - 9th International Conference, CGGA 2010, Revised Selected Papers. 2011. p. 44-54 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7033 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Aloupis, G, Bose, PK, Collette, S, Demaine, ED, Demaine, ML, Douïeb, K, Dujmović, V, Iacono, J, Langerman, S & Morin, P 2011, Common unfoldings of polyominoes and polycubes. in Computational Geometry, Graphs and Applications - 9th International Conference, CGGA 2010, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7033 LNCS, pp. 44-54, 9th International Conference on Computational Geometry, Graphs and Applications, CGGA 2010, Dalian, China, 11/3/10. https://doi.org/10.1007/978-3-642-24983-9_5

Aloupis G, Bose PK, Collette S, Demaine ED, Demaine ML, Douïeb K et al. Common unfoldings of polyominoes and polycubes. In Computational Geometry, Graphs and Applications - 9th International Conference, CGGA 2010, Revised Selected Papers. 2011. p. 44-54. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-24983-9_5

Aloupis, Greg ; Bose, Prosenjit K. ; Collette, Sébastien et al. / Common unfoldings of polyominoes and polycubes. Computational Geometry, Graphs and Applications - 9th International Conference, CGGA 2010, Revised Selected Papers. 2011. pp. 44-54 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d4f565d8ba234d22b1834048da7688e3,

title = "Common unfoldings of polyominoes and polycubes",

abstract = "This paper studies common unfoldings of various classes of polycubes, as well as a new type of unfolding of polyominoes. Previously, Knuth and Miller found a common unfolding of all tree-like tetracubes. By contrast, we show here that all 23 tree-like pentacubes have no such common unfolding, although 22 of them have a common unfolding. On the positive side, we show that there is an unfolding common to all {"}non-spiraling{"} k-ominoes, a result that extends to planar non-spiraling k-cubes.",

author = "Greg Aloupis and Bose, {Prosenjit K.} and S{\'e}bastien Collette and Demaine, {Erik D.} and Demaine, {Martin L.} and Karim Dou{\"i}eb and Vida Dujmovi{\'c} and John Iacono and Stefan Langerman and Pat Morin",

year = "2011",

doi = "10.1007/978-3-642-24983-9_5",

language = "English (US)",

isbn = "9783642249822",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "44--54",

booktitle = "Computational Geometry, Graphs and Applications - 9th International Conference, CGGA 2010, Revised Selected Papers",

note = "9th International Conference on Computational Geometry, Graphs and Applications, CGGA 2010 ; Conference date: 03-11-2010 Through 06-11-2010",

}

TY - GEN

T1 - Common unfoldings of polyominoes and polycubes

AU - Aloupis, Greg

AU - Bose, Prosenjit K.

AU - Collette, Sébastien

AU - Demaine, Erik D.

AU - Demaine, Martin L.

AU - Douïeb, Karim

AU - Dujmović, Vida

AU - Iacono, John

AU - Langerman, Stefan

AU - Morin, Pat

PY - 2011

Y1 - 2011

N2 - This paper studies common unfoldings of various classes of polycubes, as well as a new type of unfolding of polyominoes. Previously, Knuth and Miller found a common unfolding of all tree-like tetracubes. By contrast, we show here that all 23 tree-like pentacubes have no such common unfolding, although 22 of them have a common unfolding. On the positive side, we show that there is an unfolding common to all "non-spiraling" k-ominoes, a result that extends to planar non-spiraling k-cubes.

AB - This paper studies common unfoldings of various classes of polycubes, as well as a new type of unfolding of polyominoes. Previously, Knuth and Miller found a common unfolding of all tree-like tetracubes. By contrast, we show here that all 23 tree-like pentacubes have no such common unfolding, although 22 of them have a common unfolding. On the positive side, we show that there is an unfolding common to all "non-spiraling" k-ominoes, a result that extends to planar non-spiraling k-cubes.

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

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

U2 - 10.1007/978-3-642-24983-9_5

DO - 10.1007/978-3-642-24983-9_5

M3 - Conference contribution

AN - SCOPUS:81255201100

SN - 9783642249822

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 44

EP - 54

BT - Computational Geometry, Graphs and Applications - 9th International Conference, CGGA 2010, Revised Selected Papers

T2 - 9th International Conference on Computational Geometry, Graphs and Applications, CGGA 2010

Y2 - 3 November 2010 through 6 November 2010

ER -

Common unfoldings of polyominoes and polycubes

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this