Options
Linear-time recognition of map graphs with outerplanar witness
Publikationstyp
Journal Article
Date Issued
2018-05
Sprache
English
Author(s)
TORE-URI
Journal
Volume
28
Start Page
63
End Page
77
Citation
Discrete Optimization (2018)
Publisher DOI
Map graphs generalize planar graphs and were introduced by Chen et al. (STOC 1998, J. ACM, 2002). They showed that the problem of recognizing map graphs is in by proving the existence of a planar witness graph . 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 for
-vertex graphs, and a full description of its details remains unpublished.
We give a new and purely combinatorial algorithm that decides whether a graph
is a map graph having an outerplanar witness . This is a step towards a first combinatorial recognition algorithm for general map graphs. The algorithm runs in time and space . In contrast to Thorup’s approach, it computes the witness graph in the affirmative case.
-vertex graphs, and a full description of its details remains unpublished.
We give a new and purely combinatorial algorithm that decides whether a graph
is a map graph having an outerplanar witness . This is a step towards a first combinatorial recognition algorithm for general map graphs. The algorithm runs in time and space . In contrast to Thorup’s approach, it computes the witness graph in the affirmative case.
DDC Class
000: Allgemeines, Wissenschaft