Implementing a Partitioned 2Page Book Embedding Testing AlgorithmAngelini, Patrizio and Di Bartolomeo, Marco and Di Battista, Giuseppe (2013) Implementing a Partitioned 2Page Book Embedding Testing Algorithm. In: 20th International Symposium, GD 2012, September 1921, 2012 , pp. 7989(Official URL: http://link.springer.com/chapter/10.1007/9783642...). Full text not available from this repository.
Official URL: http://link.springer.com/chapter/10.1007/9783642...
AbstractIn 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 2page 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 [13] give an interesting and complex linear time algorithm for tackling Partitioned 2page Book Embedding based on SPQRtrees. We show an efficient implementation of this algorithm and show its effectiveness by performing a number of experimental tests. Because of the relationships [13] between Partitioned 2page 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.
Actions (login required)
