Optimal Partitioning of an Undirected Graph Using Matroids

Hi,

Consider the problem of partioning an undirected finite graph G(V,E)
into the minimum number of planar graphs. Let:
v = number of vertices of G,
e = number of edges of G,
t = thickness of graph G = minimum number of planar graphs into which G
can be partitioned

For the applications I am considering, e < v log(v).

According to:

[1] H. Gabow and H. Westermann, "Forests, Frames and Games: Algorithms
for Matroid Sums and Applications", in 20th Annual ACM Symposium on
Theory of Computing, 1988, pp. 407-421,
and
[2] S. Ramanathan and E.L. Lloyd, "Scheduling Algorithms for Multihop
Radio Networks", IEEE/ACM Transactions on Networking, vol. 1, no. 2,
pp. 166-177, April 1993.,

matroids can be used to partition G into at most 3t graphs in time O(ev
log(v)).

Are there better known bounds in recent literature? Pls. let me know
the appropriate references.

regards,
Ashutosh

.

Relevant Pages