Upward Partitioned Book Embeddings

Akitaya, Hugo A. and Demaine, Erik D. and Hesterberg, Adam and Liu, Quanquan C. (2017) Upward Partitioned Book Embeddings. In: Graph Drawing and Network Visualization. GD 2017, September 25-27 , pp. 210-223(Official URL: https://doi.org/10.1007/978-3-319-73915-1_18).

Full text not available from this repository.


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.

Item Type: Conference Paper
Classifications: P Styles > P.999 Others
S Software and Systems > S.120 Visualization
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1606

Actions (login required)

View Item View Item