首页    期刊浏览 2024年11月23日 星期六
登录注册

文章基本信息

  • 标题:Upward Book Embeddings of st-Graphs
  • 本地全文:下载
  • 作者:Carla Binucci ; Giordano Da Lozzo ; Emilio Di Giacomo
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2019
  • 卷号:129
  • 页码:1-22
  • DOI:10.4230/LIPIcs.SoCG.2019.13
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:We study k-page upward book embeddings (kUBEs) of st-graphs, that is, book embeddings of single-source single-sink directed acyclic graphs on k pages with the additional requirement that the vertices of the graph appear in a topological ordering along the spine of the book. We show that testing whether a graph admits a kUBE is NP-complete for k >= 3. A hardness result for this problem was previously known only for k = 6 [Heath and Pemmaraju, 1999]. Motivated by this negative result, we focus our attention on k=2. On the algorithmic side, we present polynomial-time algorithms for testing the existence of 2UBEs of planar st-graphs with branchwidth b and of plane st-graphs whose faces have a special structure. These algorithms run in O(f(b)* n+n^3) time and O(n) time, respectively, where f is a singly-exponential function on b. Moreover, on the combinatorial side, we present two notable families of plane st-graphs that always admit an embedding-preserving 2UBE.
  • 关键词:Upward Book Embeddings; st-Graphs; SPQR-trees; Branchwidth; Sphere-cut Decomposition
国家哲学社会科学文献中心版权所有