Linear-time recognition of map graphs with outerplanar witness

Mnich, Matthias; Rutter, Ignaz; Schmidt, Jens M. GND

Map graphs generalize planar graphs and were introduced by Chen, Grigni and Papadimitriou [STOC 1998, J.ACM 2002]. They showed that the problem of recognizing map graphs is in NP by proving the existence of a planar witness graph W. Shortly after, Thorup [FOCS 1998] published a polynomial-time recognition algorithm for map graphs. However, the run time of this algorithm is estimated to be Omega(n^{120}) for n-vertex graphs, and a full description of its details remains unpublished. We give a new and purely combinatorial algorithm that decides whether a graph G is a map graph having an outerplanar witness W. This is a step towards a first combinatorial recognition algorithm for general map graphs. The algorithm runs in time and space O(n+m). In contrast to Thorup's approach, it computes the witness graph W in the affirmative case.


Citation style:

Mnich, Matthias / Rutter, Ignaz / Schmidt, Jens M.: Linear-time recognition of map graphs with outerplanar witness. Ilmenau 2016. ilmedia.

Access Statistic

Last 12 Month:

open graphic


Use and reproduction: