Linear-time recognition of map graphs with outerplanar witness

DOI10.1016/j.disopt.2017.12.002zbMath1506.68187OpenAlexW2778543035MaRDI QIDQ1662161

Jens M. Schmidt, Matthias Mnich, Ignaz Rutter

Publication date: 17 August 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6034/

zbMATH Keywords

planar graphscertifying algorithmsmap graphs

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Map graphs having witnesses of large girth ⋮ Book embeddings of \(k\)-framed graphs and \(k\)-map graphs ⋮ Optimal 1-planar multigraphs ⋮ Recognizing map graphs of bounded treewidth ⋮ Characterizing and recognizing 4-map graphs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Certifying algorithms
• Characterizations of outerplanar graphs
• On-line maintenance of triconnected components with SPQR-trees
• A new planarity test
• Algorithms for graphs embeddable with few crossings per edge
• Recognizing hole-free 4-map graphs in cubic time
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Map graphs
• On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
• Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
• Efficient Planarity Testing
• On-Line Planarity Testing
• Algorithms for Square Roots of Graphs
• Dividing a Graph into Triconnected Components
• Linear-Time Recognition of Map Graphs with Outerplanar Witness

This page was built for publication: Linear-time recognition of map graphs with outerplanar witness