Map graphs having witnesses of large girth

作     者：Le, Hoang-Oanh Le, Van Bang 

作者机构：Univ Rostock Inst Informat Rostock Germany 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2019年第772卷

页      面：143-148页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Map graph Half-square Graph class Graph algorithm 

摘      要：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 NP by proving the existence of a witness. Soon later, Thorup [FOCS 1998] claimed that recognizing map graphs is in P, 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 g = 8. 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. (C) 2018 Elsevier B.V. All rights reserved.