On exteriority notions in book embeddings and treewidth

Nicolas Baudru (1, 2) , Severine Fratani (1, 2)

1 LIS - Laboratoire d'Informatique et Systèmes
2 MOVE - Modélisation et Vérification

Book embeddings generalize planar embeddings to a space formed by several half-planes sharing their boundary. While several measures on planar graphs allow to define treewidth-bounded classes of pla-nar graphs, no such results exist for book embeddings. Indeed, many of these measures rely on the notion of exteriority that cannot be simply generalized to books due to their complex topology. In this paper, we first propose a notion of exteriority for book embeddings, and then, define an outerplanar-like measure: a book embedding is k-outeredge if the distance from its edges to the outside is at most k. We exhibit a large class of k-outeredge book embeddings that is treewidth-bounded by Ω(2 k) and O(p k), for a fixed number p of half-planes. The lower bound comes from a nice connection with formal verification results.

Keywords: Graph theory; Book embedding; Exteriority; Outerplanar-like measure; Treewidth

Domains: Computer Science [cs]; Discrete Mathematics [cs.DM]; Formal Languages and Automata Theory [cs.FL]

Nicolas Baudru, Severine Fratani. On exteriority notions in book embeddings and treewidth. Discrete Mathematics, 2020, 343 (4), pp.111703. ⟨10.1016/j.disc.2019.111703⟩. ⟨hal-02401981⟩