Abstract
The square of a graph H, denoted H^2, is obtained from H by adding new edges between two distinct vertices whenever their distance in H is two. The halfsquares of a bipartite graph B=(X,Y,E_B) are the subgraphs of B^2 induced by the color classes X and Y, B^2[X] and B^2[Y]. For a given graph G=(V,E_G), if G=B^2[V] for some bipartite graph B=(V,W,E_B), then B is a representation of G and W is the set of points in B. If in addition B is planar, then G is also called a map graph and B is a witness of G [Chen, Grigni, Papadimitriou. Map graphs. J. ACM , 49 (2) (2002) 127138].
While Chen, Grigni, Papadimitriou proved that any map graph G=(V,E_G) has a witness with at most 3V6 points, we show that, given a map graph G and an integer k, deciding if G admits a witness with at most k points is NPcomplete. As a byproduct, we obtain NPcompleteness of edge clique partition on planar graphs; until this present paper, the complexity status of edge clique partition for planar graphs was previously unknown.
We also consider halfsquares of treeconvex bipartite graphs and prove the following complexity dichotomy: Given a graph G=(V,E_G) and an integer k, deciding if G=B^2[V] for some treeconvex bipartite graph B=(V,W,E_B) with W<=k points is NPcomplete if G is nonchordal dually chordal and solvable in linear time otherwise. Our proof relies on a characterization of halfsquares of treeconvex bipartite graphs, saying that these are precisely the chordal and dually chordal graphs.
BibTeX  Entry
@InProceedings{le_et_al:LIPIcs:2019:10957,
author = {HoangOanh Le and Van Bang Le},
title = {{Constrained Representations of Map Graphs and HalfSquares}},
booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
pages = {13:113:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771177},
ISSN = {18688969},
year = {2019},
volume = {138},
editor = {Peter Rossmanith and Pinar Heggernes and JoostPieter Katoen},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10957},
URN = {urn:nbn:de:0030drops109574},
doi = {10.4230/LIPIcs.MFCS.2019.13},
annote = {Keywords: map graph, halfsquare, edge clique cover, edge clique partition, graph classes}
}
Keywords: 

map graph, halfsquare, edge clique cover, edge clique partition, graph classes 
Collection: 

44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) 
Issue Date: 

2019 
Date of publication: 

20.08.2019 