Mnich, MatthiasMatthiasMnichRutter, IgnazIgnazRutterSchmidt, Jens M.Jens M.Schmidt2020-10-192020-10-192016-0615th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) 53: 5.1-5.4 (2016http://hdl.handle.net/11420/7612Map 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 Ω(n120) 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.enAlgorithms and data structuresMap graphsPlanar graphsRecognitionMathematikConference Paper10.4230/LIPIcs.SWAT.2016.5Other