Computational Complexity of Graph Planarity Testing

• Thesis title in Czech: Výpočetní složitost testování rovinnosti grafu
• Thesis title in English: Computational Complexity of Graph Planarity Testing
• Academic year of topic announcement: 2005/2006
• Thesis type: Bachelor's thesis
• Thesis language: angličtina
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: Mgr. Martin Bálek
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 03.11.2005
• Date of assignment: 03.11.2005
• Date and time of defence: 27.06.2006 00:00
• Date of electronic submission: 27.06.2006
• Date of submission of printed version: 27.06.2006
• Date of proceeded defence: 27.06.2006
• Opponents: Mgr. Petr Škovroň, Ph.D.

Guidelines

Práce bude v angličtině.

References

V. Ramachandran, J. Reiff: Planarity Testing in Parallel, J. Computer and Systems Sciences vol.49, 1994
J. Reiff: Symmetric Complementation, J. of ACM, 1984
E. Allender, M. Mahajan: The Complexity of Planarity Testing
M. Sipser: Introduction to the Thory of Computation, PWS Publishing, 1997

Preliminary scope of work

Problému planarity grafu je v LOGSPACE. Práce bude obsahovat (LOGSPACE) algoritmus
redukce libovolného grafu na graf s maximálním stupněm 3.
Jedná se o zjednodušení postupu z článku Allenrder, Mahajan: The Complexity of Planarity Testing.