Computational Complexity of Graph Planarity Testing

• Název práce v češtině: Výpočetní složitost testování rovinnosti grafu
• Název v anglickém jazyce: Computational Complexity of Graph Planarity Testing
• Akademický rok vypsání: 2005/2006
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: Mgr. Martin Bálek
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 03.11.2005
• Datum zadání: 03.11.2005
• Datum a čas obhajoby: 27.06.2006 00:00
• Datum odevzdání elektronické podoby: 27.06.2006
• Datum odevzdání tištěné podoby: 27.06.2006
• Datum proběhlé obhajoby: 27.06.2006
• Oponenti: Mgr. Petr Škovroň, Ph.D.

Zásady pro vypracování

Práce bude v angličtině.

Seznam odborné literatury

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

Předběžná náplň práce

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.