Výpočetní složitost testování rovinnosti grafu

Krčál, Marek

In this paper we will show that the problem of planarity testing is in SL (symmetric nondeterministic LOGSPACE). The main part of our proof is a reduction of the problem to planarity of graphs with maximal degree three. Note that usual replacing vertices of degree bigger than three by "little circles" can spoil planarity, we need to be smarter. Planarity of graphs with maximal degree three was already solved in paper "Symmetric complementation" by John Reif. Previously Meena Mahajan and Eric Allender have already proved this in ("Complexity of planarity testing"), but their proof is the pure SL implementation of a parallel algorithm by John Reif and Vijaya Ramachandran ("Planarity testing in parallel"). But it is possibly unnecessarily complex and sophisticated for the purposes of the space complexity. This result together with recent breakthrough by Omer Reingold that SL = L ("Undirected T-connectivity in log-space") completely solves the question of complexity of planarity problem, because planarity is hard for L (it is again shown in "Complexity of planarity testing"). We construct logarithmic-space computable function that converts input graph G into G0 with maximal degree three such that G is planar if and only if G0 is. This together with.

guest :: login Digital Repository
		Search		Submit		Help		About