Valid Orderings of Layers When Simple-Folding a Map

• Jia Yiyang

  University of Tsukuba

• Mitani Jun

  University of Tsukuba

• Uehara Ryuhei

  School of Information Science, JAIST

Abstract

In this work, we consider a decision problem on whether an overlapping order of all the squares of an m × n map is valid under a particular context called simple folding. This problem belongs to the field of map folding. It is a variation of both the decision problem of valid orders of a 1 × n map under the context of simple folds and the decision problem of valid orders of an m × n map under the context of general folds. We provide a method and its corresponding linear-time algorithm to solve this problem, which is based on the construction of a directed graph representing the adjacency relations among squares.

Journal

• Journal of Information Processing

  Journal of Information Processing 28 (0), 816-824, 2020

  Information Processing Society of Japan

Keywords

• map folding problem
• overlapping order
• <i>m</i> × <i>n</i> map
• linear-time algorithm

Details

• CRID: 1390849931313316352
• NII Article ID: 130007956337
• DOI: 10.2197/ipsjjip.28.816
• ISSN: 18826652
• Web Site: https://www.jstage.jst.go.jp/article/ipsjjip/28/0/28_816/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed