HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

On exteriority notions in book embeddings and treewidth

Abstract : 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.
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download

Contributor : Nicolas Baudru Connect in order to contact the contributor
Submitted on : Tuesday, December 10, 2019 - 11:50:07 AM
Last modification on : Saturday, March 19, 2022 - 3:08:42 AM
Long-term archiving on: : Wednesday, March 11, 2020 - 8:28:43 PM


Files produced by the author(s)




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



Record views


Files downloads