My name is Marek Krcál and I'm member of group of Czech students participating at Research Experience for Undergraduates at Dimacs, Rutgers.
The other members of the group are Jan Hladký, Josef Cibulka, our group leader is Martin Bálek. Our advisors are Eric Allender and Jeff Kahn
I'm working on this computer science problem:
Recently I have found a bug in paper by Ramachandran & Reif (RR94): a partial claim doesn't hold. I can't see any obvious "patch", but the bug might not affect the final result. I'd like to figure out that by further careful study of the paper.
I haven't still gone through the whole [RR94] paper, but it seems to me very probable, that the result of the paper is OK. Even the partial claim on page 8 could be corrected, I think, by adding a test of Euler formula for the star graph combinatorically embedded according to 2-coloring of its interlacing parity graph. (Which is Martin's idea and he found it in prof. Allender's paper The complexity of planarity testing)
I chose a new way, influenced by my advisor's idea and inspired by a technique described in [RR94] paper. An idea is to use older planarity testing for max. degree 3-graphs and just to come up with reduction from general graph planarity. A technique is local graph replacement, which is part of [RR94] algorithm and which does a partial reduction of degree of some vertices. I'll try to improve the technique to do the job.