Simpler algorithms for testing two-page book embedding of partitioned graphs

摘要

A 2-page book embedding of a graph is to place the vertices linearly on a spine (a line segment) and the edges on the two pages (two half planes sharing the spine) so that each edge is embedded in one of the pages without edge crossings. Testing whether a given graph admits a 2-page book embedding is known to be NP-complete.