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 metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal-amu.archives-ouvertes.fr/hal-02401981
Contributor : Nicolas Baudru <>
Submitted on : Tuesday, December 10, 2019 - 11:50:07 AM
Last modification on : Monday, January 13, 2020 - 1:19:15 AM
Document(s) archivé(s) le : Wednesday, March 11, 2020 - 8:28:43 PM

File

HAL_treewidthOfBookEmbbeding.p...
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

91

Files downloads

13