Photos from REU 2005.

REU Project Page of Marek Krcal

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:

Planarity testing

Quite recently it was proven, that testing of planarity of a graph is in a complexity class L. L is class of problems that can be solved using Turing machine with logarihmic space. The classification of the planarity testing was proved by applicating very complicated (originally parallel optimized) algorithm by Ramachandran & Reif. My goal would be to simplify the proof.

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.