Tamara Mchedlidze (Karlsruhe Institute of Technology)
Colloquium of Department of Mathematics and Computer Science
Thursday December 5 15:30 room 105 (14-th line V.I., 29)
A k-page upward book embedding (kUBE) is a topological representation of a directed graph in a k-page book: the vertices are drawn along the spine of the book, the edges are represented by semi-circles on the pages of the book and the requirements are that all edges point in the same direction and no two edges on the same page intersect. Computing kUBE of directed graphs is a widely studied combinatorial problem, which finds applications in a variety of domains ranging from VLSI design to computational origami.
In this talk, I will concentrate on our recent positive results on 2UBEs of planar st-graphs, a wide class of planar directed acyclic graphs. On the algorithmic side, I will present polynomial-time algorithms for testing the existence of 2UBEs of planar st-graphs with branchwidth β and of plane st-graphs whose faces have a special structure. On the combinatorial side, I will present two notable families of plane st-graphs that always admit a 2UBE.
Everyone is welcome!
