2026-07-24T00:04:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6034 2024-03-06T10:37:28Z ddc:004 open_access

Linear-Time Recognition of Map Graphs with Outerplanar Witness Mnich, Matthias Rutter, Ignaz Schmidt, Jens M. Algorithms and data structures map graphs recognition planar graphs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matthias Mnich and Ignaz Rutter and Jens M. Schmidt 2016 Is Part Of LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2016.5 urn:nbn:de:0030-drops-60349 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.5 eng https://creativecommons.org/licenses/by/3.0/legalcode