Campus Event Calendar
Event Entry
What and Who
Drawing Interval Graphs
Rajiv Raman
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 30 April 2008
14:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
An interval graph is an intersection graph of intervals on the real line.
Recognizing a graph as an interval graph and constructing an interval
representation can be solved in polynomial time.
A natural generalization that arises in several applications is an
additional specification on the length of each interval in the
representation. I will present ongoing work on two problems, namely
drawing an interval graph with specified lenghts on the intervals such
that we minimize the maximum stretch, and the problem of extracting the
largest subgraph that can be drawn with prescribed lengths. This is joint
work with Saurabh Ray.
Contact
Khaled Elbassioni
--email hidden
passcode not visible
logged in users only
Khaled Elbassioni, 04/29/2008 16:43
Khaled Elbassioni, 04/29/2008 16:42 -- Created document.
Khaled Elbassioni, 04/29/2008 16:42 -- Created document.