Linear-time recognition of map graphs with outerplanar witness

Publikationstyp
Conference Paper
Date Issued
2016-06
Sprache
English
Author(s)
Mnich, Matthias  orcid-logo
Rutter, Ignaz  
Schmidt, Jens M.  orcid-logo
TORE-URI
http://hdl.handle.net/11420/7612
First published in
Leibniz international proceedings in informatics (LIPIcs)  
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
15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)  
Publisher DOI
10.4230/LIPIcs.SWAT.2016.5
Scopus ID
2-s2.0-85012026196
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