Maximum Induced Multicliques and Complete Multipartite Subgraphs in Polygon-Circle Graphs and Circle Graphs

摘要

A graph is a multiclique if its connected components are cliques. A graph is a complete multipartite graph if it is the complement of a multiclique. A graph is a multiclique-multipartite graph if its vertex set has a partition U, W such that G(U) is complete multipartite, G(W) is a multiclique and every two vertices u∈U, v∈W are adjacent. We describe a polynomial time algorithm to find in polygon-circle graphs a maximum induced complete multipartite subgraph containing an induced K_(2,2). In addition, we describe polynomial time algorithms to find maximum induced multicliques and multiclique-multipartite subgraphs in circle graphs. These problems have applications for clustering of proteins by PPI criteria.