Map graphs having witnesses of large girth

DOI10.1016/J.TCS.2018.12.010MaRDI QIDQ2632022zbMATH OpenOpenAlexFDO

Authors 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)

Abstract: A half-square of a bipartite graph $B=(X,Y,E_B)$ has one color class of $B$ as vertex set, say $X$; two vertices are adjacent whenever they have a common neighbor in $Y$. If $G=(V,E_G)$ is the half-square of a planar bipartite graph $B=(V,W,E_B)$, then $G$ is called a map graph, and $B$ is a witness of $G$. Map graphs generalize planar graphs, and have been introduced and investigated by Chen, Grigni and Papadimitriou [STOC 1998, J. ACM 2002]. They proved that recognizing map graphs is in $mathsfNP$ by proving the existence of a witness. Soon later, Thorup [FOCS 1998] claimed that recognizing map graphs is in $mathsfP$, by providing an $Omega(n^{120})$-time algorithm for $n$-vertex input graphs. In this note, we give good characterizations and efficient recognition for half-squares of bipartite graphs with girth at least a given integer $gge8$. It turns out that map graphs having witnesses of girth at least $g$ are precisely the graphs whose vertex-clique incidence bipartite graph is planar and of girth at least $g$. Our structural characterization implies an $O(n^{2}m)$-time algorithm for recognizing if a given $n$-vertex $m$-edge graph $G$ is such a map graph.

Recommendations

• Linear-time recognition of map graphs with outerplanar witness
• Linear-time recognition of map graphs with outerplanar witness
• scientific article; zbMATH DE number 1775439

Cites work

• \(\mathsf{NIC}\)-planar graphs
• A New Algorithm for Generating All the Maximal Independent Sets
• Approximation algorithms for independent sets in map graphs
• Arboricity and Subgraph Listing Algorithms
• Finding a Minimum Circuit in a Graph
• Finding cliques in social networks: a new distribution-free model
• Finding Even Cycles Even Faster
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• FO model checking on map graphs
• scientific article; zbMATH DE number 1305408 (Why is no real title available?)
• scientific article; zbMATH DE number 1775439 (Why is no real title available?)
• scientific article; zbMATH DE number 7053376 (Why is no real title available?)
• Linear-time recognition of map graphs with outerplanar witness
• Linearity of grid minors in treewidth with applications through bidimensionality
• Map graphs
• Min-cuts and shortest cycles in planar graphs in O(n n) time
• On graphs without a \(C_{4}\) or a diamond
• On the complexity of fixed parameter clique and dominating set
• Quick k-Median, k-Center, and Facility Location for Sparse Graphs
• Recognizing hole-free 4-map graphs in cubic time
• Recognizing optimal 1-planar graphs in linear time

Cited in

(4)

• Linear-time recognition of map graphs with outerplanar witness
• Constrained representations of map graphs and half-squares
• Linear-time recognition of map graphs with outerplanar witness
• Recognizing map graphs of bounded treewidth

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2632022)