Options
Linear-time recognition of map graphs with outerplanar witness
Publikationstyp
Conference Paper
Date Issued
2016-06
Sprache
English
Author(s)
TORE-URI
First published in
Number in series
53
Start Page
5.1
End Page
5.14
Citation
15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) 53: 5.1-5.4 (2016
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
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 Ω(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.
Subjects
Algorithms and data structures
Map graphs
Planar graphs
Recognition
DDC Class
510: Mathematik