Login
Talks & Seminars
Title: Bi-Connected Planar Graph Isomorphism in Log-Space
Ms. Nutan Limaye, Research Fellow, Institute of Mathematical Sciences, Chennai
Date & Time: January 28, 2009 16:00
Venue: Conference Room, 01st floor, ā€˜Cā€™ Block, Kanwal Rekhi Building
Abstract:

We consider the biconnected and 3-connected planar graph isomorphism. We prove a Logspace upper bound for biconnected planar graph isomorphism and canonization, which improves the previously known upper bound of AC1 of Miller and Ramachandran. As an intermediate step, we decompose the biconnected planar graph into its triconnected component tree. We give a log-space procedure for this step, which improves the previously known upper bound of AC1 of Miller and Ramachandran.

We give a log-space algorithm for 3-connected planar graph isomorphism and canonization. The problem was known to be hard for log-space and was shown to be in UL intersection co-UL by Thierauf and Wagner. Our algorithm implies an L-completeness result for 3-connected and bi-connected planar graph isomorphism and canonization, thereby settling their complexity.

(Collaboration with Samir Datta, Prajakta Nimbhorkar, Thomar Thierauf, and Fabian Wagner)

Speaker Profile:
Details about the speaker is available at http://www.imsc.res.in/~nutan/
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback