2017/08/22 by Hugo A. Akitaya, Akitaya, Hugo A., Erik D. Demaine +5
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Advanced Materials and Mechanics #Algorithms and Data Compression #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #Ubiquitin and proteasome pathways
paper · pdf · doi:10.48550/arxiv.1708.06730
openalex publication_date 2017/08/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We analyze a directed variation of the book embedding problem when the page partition is prespecified and the nodes on the spine must be in topological order (upward book embedding). Given a directed acyclic graph and a partition of its edges into k pages, can we linearly order the vertices such that the drawing is upward (a topological sort) and each page avoids crossings? We prove that the problem is NP-complete for k≥ 3, and for k≥ 4 even in the special case when each page is a matching. By contrast, the problem can be solved in linear time for k=2 pages when pages are restricted to matchings. The problem comes from Jack Edmonds (1997), motivated as a generalization of the map folding problem from computational origami.