thesis defense - computer science: rustem kakimov

please join the computer science department for the upcoming thesis defense:

presenter: rustem kakimov

thesis title: upward book embeddings of dags: constraint-based methods and embeddability analysis

abstract: the k-page upward book embedding (kube) problem is a fundamental challenge in graph theory with applications in circuit layout, scheduling, and hierarchical visualization. despite its relevance, the problem—particularly for k ≥ 2—remains underexplored. this thesis develops practical methods for solving kube and conducts a detailed investigation of how graph structural properties influence upward embeddability.

we first propose a boolean satisfiability (sat) encoding, sat-1, that extends existing k-page book embedding techniques to the general kube setting. for the special case of k = 2 (2ube), we introduce sat-2, a more compact sat encoding exploiting the fixed number of pages, and a constraint programming (cp) model as an alternative formulation. empirical evaluation shows that sat solvers consistently outperform cp, with sat-2 achieving up to 40% faster runtimes on large instances and up to 30× speedups on hard instances from the north dataset compared to sat-1.

beyond solving efficiency, we systematically analyze how upward book embeddability depends on structural parameters such as the edge-to-vertex ratio (m/n). through exhaustive enumeration and sampling, we identify sharp phase transition phenomena across different values of k (up to k = 6) and model the phase transition threshold as a function of graph size and page count using a power-law relationship, providing the first quantitative characterization of this phenomenon.


committee members:
dr. xing tan (supervisor, committee chair), dr. ruizhong wei, dr. kai huang (mcmaster university)

please contact grad.compsci@lakeheadu.ca for the zoom link. everyone is welcome.