Campus Event Calendar
Event Entry
What and Who
Determining the smallest k such that G is k-outerplanar
Frank Kammer
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
Monday, 2 April 2007
13:30
-- Not specified --
E1 4
024
Saarbrücken
Abstract
The outerplanarity index of a planar graph G is the smallest k
such that G has a k-outerplanar embedding. We show how to compute the
outerplanarity index of an n-vertex planar graph in O(n^2) time,
improving the previous best bound of O(k^3 n^2).
We also give a linear-time 4-approximation algorithm for the same
problem and show how this can be used to solve maximum independent set, minimum dominating set and several other NP-hard problems faster on planar graphs with outerplanarity indices within a constant factor of their treewidths.
Contact
Khaled Elbassioni
--email hidden
passcode not visible
logged in users only
Khaled Elbassioni, 03/23/2007 20:37 -- Created document.