Characterizing and recognizing 4-map graphs

DOI10.1007/s00453-018-0510-xzbMath1423.05050OpenAlexW2889102722WikidataQ129336940 ScholiaQ129336940MaRDI QIDQ1741846

Franz-Josef Brandenburg

Publication date: 7 May 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-018-0510-x

zbMATH Keywords

mapsplanar graphsgraph algorithms1-planar graphsmap graphs

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Recognizing and embedding simple optimal 2-planar graphs, On morphing 1-planar drawings, Improved product structure for graphs on surfaces, Straight-line drawings of 1-planar graphs, Book embeddings of \(k\)-framed graphs and \(k\)-map graphs, Graph product structure for non-minor-closed classes, Optimal 1-planar multigraphs, Recognizing map graphs of bounded treewidth, Unnamed Item, Characterizing 5-map graphs by 2-fan-crossing graphs, Unnamed Item, 1-planarity testing and embedding: an experimental study, Counting cliques in 1-planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Outer 1-planar graphs
• A linear-time algorithm for testing outer-1-planarity
• The structure of 1-planar graphs
• Bemerkungen zu einem Sechsfarbenproblem von G. Ringel
• Linear-time recognition of map graphs with outerplanar witness
• Recognizing optimal 1-planar graphs in linear time
• On-line maintenance of triconnected components with SPQR-trees
• Ein Sechsfarbenproblem auf der Kugel
• An annotated bibliography on 1-planarity
• \(\mathsf{NIC}\)-planar graphs
• Algorithms for graphs embeddable with few crossings per edge
• Recognizing hole-free 4-map graphs in cubic time
• Straight-Line Grid Drawings of 3-Connected 1-Planar Graphs
• Re-embeddings of Maximum 1-Planar Graphs
• Map graphs
• Über 1-optimale Graphen
• Arboricity and Subgraph Listing Algorithms
• Zur Struktur 1‐planarer Graphen
• Rectilinear drawings of graphs
• Recognizing IC-Planar and NIC-Planar Graphs
• On-Line Planarity Testing
• Dividing a Graph into Triconnected Components
• On the Density of Maximal 1-Planar Graphs
• Computing Vertex Connectivity: New Bounds from Old Techniques
• 1-Planarity of Graphs with a Rotation System
• Enumeration of simple complete topological graphs