Publications with Ryuhei Uehara
- Flat foldings of plane graphs with prescribed angles and edge lengths.
Z. Abel, E. Demaine, M. Demaine, D. Eppstein, A. Lubiw, and R. Uehara.
arXiv:1408.6771.
22nd Int. Symp. Graph Drawing, Würzburg, Germany, 2014.
Springer, Lecture Notes in Comp. Sci. 8871, 2014, pp. 272–283.
J. Computational Geometry 9 (1): 74–93, 2018.Given a plane graph with fixed edge lengths, and an assignment of the angles 0, 180, and 360 to the angles between adjacent edges, we show how to test whether the angle assignment can be realized by an embedding of the graph as a flat folding on a line. As a consequence, we can determine whether two-dimensional cell complexes with one vertex can be flattened. The main idea behind the result is to show that each face of the graph can be folded independently of the other faces.
- Folding a paper strip to minimize thickness.
E. Demaine, D. Eppstein, A. Hesterberg, H. Ito, A. Lubiw, R. Uehara, and Y. Uno.
arXiv:1411.6371.
9th International Workshop on Algorithms and Computation (WALCOM 2015), Dhaka, Bangladesh.
Springer, Lecture Notes in Comp. Sci. 8973 (2015), pp. 113–124.
Journal of Discrete Algorithms 36: 18–26, 2016 (special issue for WALCOM).
If a folding pattern for a flat origami is given, together with a mountain-valley assignment, there might still be multiple ways of folding it, depending on how some flaps of the pattern are arranged within pockets formed by folds elsewhere in the pattern. It turns out to be hard (but fixed-parameter tractable) to determine which of these ways is best with respect to minimizing the thickness of the folded pattern.
- Reconfiguring undirected paths.
E. Demaine, D. Eppstein, A. Hesterberg, K. Jain, A. Lubiw, R. Uehara, and Y. Uno.
arXiv:1905.00518.
16th Algorithms and Data Structures Symp. (WADS 2019), Edmonton, Alberta.
Springer, Lecture Notes in Comp. Sci. 11646 (2019), pp. 353–365.
A motion that slides an undirected path along its length from one configuration to another in a graph (allowing moves in both directions) can be found in time that is fixed-parameter tractable in the path length. However the problem is PSPACE-complete for paths of unbounded length, even when the host graph has bounded bandwidth.
(Slides)
- Ununfoldable Polyhedra with 6 Vertices or 6 Faces.
H. A. Akitaya, E. Demaine, D. Eppstein, T. Tachi, and R. Uehara.
22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG3), Tokyo, Japan, 2019, pp. 27–28.
Comp. Geom. Theory & Applications 103: 101857, 2022.
We find a (nonconvex, but topologically equivalent to convex) polyhedron with seven vertices and six faces that cannot be unfolded to a flat polygon by cutting along its edges. Both the number of vertices and the number of faces are the minimum possible. The JCDCG3 version used the title "Minimal ununfoldable polyhedron".
- Multifold tiles of polyominoes and convex lattice polygons.
K. Chida, E. Demaine, M. Demaine, D. Eppstein, A. Hesterberg, T. Horiyama, J. Iacono, H. Ito, S. Langerman, R. Uehara, and Y. Uno.
23rd Thailand-Japan Conference on Discrete and Computational Geometry, Graphs, and Games, 2021, pp. 28–29.
Thai Journal of Mathematics 21 (4): 957–978, 2023.We investigate shapes whose congruent copies can cover the plane exactly \(k\) times per point, but not a number of times that is a nonzero integer smaller than \(k\). We find polyominoes with this property for all \(k\ge 2\), and convex integer-coordinate polygons with this property for \(k=5\) and for all \(k\ge 7\).