A Note on Directed Treewidth

We characterise digraphs of directed treewidth one in terms of forbidden butterfly minors. Moreover, we show that there is a linear relation between the hypertree-width of the dual of the cycle hypergraph of D, i. e. the hypergraph with vertices V (D) where every hyperedge corresponds to a directed...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-10
Main Author: Wiederrecht, Sebastian
Format: Article
Language:English
Subjects:
Apexes
Graph theory
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We characterise digraphs of directed treewidth one in terms of forbidden butterfly minors. Moreover, we show that there is a linear relation between the hypertree-width of the dual of the cycle hypergraph of D, i. e. the hypergraph with vertices V (D) where every hyperedge corresponds to a directed cycle in D, and the directed treewidth of D. Based on this we show that a digraph has directed treewidth one if and only if its cycle hypergraph is a hypertree.
ISSN:2331-8422