@inproceedings{c87e77fb88c04e1a8781b4e7cdab9785,

title = "On edge-unfolding one-layer lattice polyhedra with cubic holes",

abstract = "An edge-unfolding of a polyhedron is a cutting of the polyhedron's surface along its edges so that its surface can be flattened into a single connected flat patch on the plane without any self-overlapping. A one-layer lattice polyhedron is a polyhedron of height one, whose surface faces are grid squares. We consider the edge-unfolding problem on several classes of one-layer lattice polyhedra with cubic holes. We propose linear-time algorithms for one-layer lattice polyhedra with rectangular external boundary and cubic holes, one-layer lattice polyhedra with cubic holes strictly enclosed by an orthogonally convex polygon, and one-layer lattice polyhedra with sparse cubic holes, respectively. The algorithms use two different novel techniques to cut the edges of cubic holes of the given polyhedron so that no self-overlapping can occur in the flattened patch. Our algorithms are the first algorithms especially designed to edge-unfold a polyhedron of genus greater than zero to a single connected flattened patch. We leave open the question whether any of these edge-cutting methods can be extended to edge-unfold general one-layer lattice polyhedra with cubic holes.",

author = "Liou, {Meng Huan} and Poon, {Sheung Hung} and Wei, {Yu Jie}",

year = "2014",

doi = "10.1007/978-3-319-08783-2_22",

language = "English",

isbn = "9783319087825",

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

publisher = "Springer Verlag",

pages = "251--262",

booktitle = "Computing and Combinatorics - 20th International Conference, COCOON 2014, Proceedings",

address = "Germany",

note = "20th International Computing and Combinatorics Conference, COCOON 2014 ; Conference date: 04-08-2014 Through 06-08-2014",

}