On exteriority notions in book embeddings and treewidth - MOVE Modélisation et Vérification - LIS Laboratoire d'Informatique et Systèmes de Marseille (UMR 7020) Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics Année : 2020

On exteriority notions in book embeddings and treewidth

Résumé

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.
Fichier principal
Vignette du fichier
HAL_treewidthOfBookEmbbeding.pdf (439.88 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02401981 , version 1 (10-12-2019)

Identifiants

Citer

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⟩
89 Consultations
98 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More