Presenter: Robert SCHEFFLER
PhD student at the Chair of Discrete Mathematics and Foundations of Computer Science at Brandenburg University of Technology in Cottbus, Germany.
Title: The Distance Orientation Problem
Abstract:
We study the Distance Orientation Problem (DOP) which is motivated by an applications in the field of computer vision. Given a weighted graph, the question is whether there is a function that assigns heights to the vertices, such that the absolute difference between the heights of adjacent vertices is equal to the weight of the edge between these vertices. This problem can also be formulated as the task of finding a special orientation of the graph. We will present some complexity results for the DOP on planar graphs. Furthermore, we will see that outerplanar embeddings have a special property in respect to this problem, which characterizes them.
Presenter: Jesse BEISEGEL
PhD student at Brandenburg University of Technology in Cottbus, Germany.
Title: Characterising AT-Free Graphs with BFS
Abstract:
An asteroidal triple free graph is a graph such that for every independent triple of vertices no path between any two avoids the third. In a recent result, these graphs were characterised through a linear vertex ordering called an AT-free order. Here, we use techniques from abstract convex geometry to improve on this result by giving a vertex order characterisation with stronger structural properties and thus resolve an open question Corneil and Stacho. These orderings are generated by a modification of BFS which runs in polynomial time. Furthermore, we give a linear time algorithm which employs multiple applications of (L)BFS to compute AT-free orders in claw-free AT-free graphs and a generalisation of these.