Implementing a partitioned 2-page book embedding testing algorithm

DOI10.1007/978-3-642-36763-2_8MaRDI QIDQ4912192zbMATH OpenOpenAlexWikidataFDO

Authors Patrizio Angelini, Marco di Bartolomeo, Giuseppe Di Battista

Publication date 3 April 2013

Published in Graph Drawing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1209.0598

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Abstract: In a book embedding the vertices of a graph are placed on the "spine" of a "book" and the edges are assigned to "pages" so that edges on the same page do not cross. In the Partitioned 2-page Book Embedding problem egdes are partitioned into two sets E_1 and E_2, the pages are two, the edges of E_1 are assigned to page 1, and the edges of E_2 are assigned to page 2. The problem consists of checking if an ordering of the vertices exists along the spine so that the edges of each page do not cross. Hong and Nagamochi give an interesting and complex linear time algorithm for tackling Partitioned 2-page Book Embedding based on SPQR-trees. We show an efficient implementation of this algorithm and show its effectiveness by performing a number of experimental tests. Because of the relationships between Partitioned 2-page Book Embedding and clustered planarity we yield as a side effect an implementation of a clustered planarity testing where the graph has exactly two clusters.

Recommendations

• Simpler algorithms for testing two-page book embedding of partitioned graphs
• Simpler algorithms for testing two-page book embedding of partitioned graphs
• Embedding planar graphs in four pages
• Upward partitioned book embeddings
• Embedding planar 5-graphs in three pages

Cited in

(9)

• Simpler algorithms for testing two-page book embedding of partitioned graphs
• Simpler algorithms for testing two-page book embedding of partitioned graphs
• scientific article; zbMATH DE number 5808757 (Why is no real title available?)
• Upward partitioned book embeddings
• Upward book embeddings of st-graphs
• A Sublinear Bound on the Page Number of Upward Planar Graphs
• Upward book embeddability of \(st\)-graphs: complexity and algorithms
• A tight subexponential-time algorithm for two-page book embedding
• Constrained planarity in practice -- engineering the synchronized planarity algorithm

This page was built for publication: Implementing a partitioned 2-page book embedding testing algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4912192)