Thema der Dissertation:
Signotopes and Convex Drawings Thema der Disputation:
The leafage of chordal graphs
Signotopes and Convex Drawings Thema der Disputation:
The leafage of chordal graphs
Abstract: Every chordal graph can be represented as an intersection graph of subtrees of a host tree.
The leafage, which was introduced by Lin, McKee and West, is the minimum number of leaves of the host tree among all such representations.
For the subclass of interval graphs, a possible host tree is a path.
Since interval graphs are precisely the chordal graphs with leafage at most 2, the leafage is a measure of how far a chordal graph is from being an interval graph.
Several problems which are NP-hard in general can be solved efficiently for interval graphs.
In various cases the algorithms for interval graphs can be adapted to work for chordal graphs with bounded leafage.
We discuss some structural results of the host tree and present the polynomial time algorithm of Habib and Stacho to compute a host tree with a minimum number of leaves.
The leafage, which was introduced by Lin, McKee and West, is the minimum number of leaves of the host tree among all such representations.
For the subclass of interval graphs, a possible host tree is a path.
Since interval graphs are precisely the chordal graphs with leafage at most 2, the leafage is a measure of how far a chordal graph is from being an interval graph.
Several problems which are NP-hard in general can be solved efficiently for interval graphs.
In various cases the algorithms for interval graphs can be adapted to work for chordal graphs with bounded leafage.
We discuss some structural results of the host tree and present the polynomial time algorithm of Habib and Stacho to compute a host tree with a minimum number of leaves.
Zeit & Ort
19.01.2024 | 14:15
Seminarraum 031
(Fachbereich Mathematik und Informatik, Arnimallee 7, 14195 Berlin)