Map graphs having witnesses of large girth

DOI10.1016/j.tcs.2018.12.010zbMath1423.05180arXiv1812.04102OpenAlexW2903680457MaRDI QIDQ2632022

Hoàng-Oanh Le, Van Bang Le

Publication date: 17 May 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1812.04102

zbMATH Keywords

graph algorithmgraph classhalf-squaremap graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Recognizing map graphs of bounded treewidth ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On graphs without a \(C_{4}\) or a diamond
• On the complexity of fixed parameter clique and dominating set
• Linearity of grid minors in treewidth with applications through bidimensionality
• Linear-time recognition of map graphs with outerplanar witness
• FO model checking on map graphs
• Recognizing optimal 1-planar graphs in linear time
• \(\mathsf{NIC}\)-planar graphs
• Recognizing hole-free 4-map graphs in cubic time
• Approximation Algorithms for Independent Sets in Map Graphs
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) Time
• Map graphs
• Arboricity and Subgraph Listing Algorithms
• A New Algorithm for Generating All the Maximal Independent Sets
• Finding a Minimum Circuit in a Graph
• Finding Even Cycles Even Faster
• Quick k-Median, k-Center, and Facility Location for Sparse Graphs
• Hardness and structural results for half-squares of restricted tree convex bipartite graphs

This page was built for publication: Map graphs having witnesses of large girth