O problema da inundação em grafos função-circular

Abstract

The Flood it Problem aims to determine the smallest number of movements required to convert a colored surface into a monochromatic one. Such surface can be modeled as a graph, where each vertex is a continous monochromatic region. If two regions are neighbors, then there is an edge connecting the vertices representing these regions. In a graph modeled from a colored surface, a connected subgraph composed by vertices of the same color is called monochromatic component. A movement is the assignment of a color to the vertices of a monochromatic component. There are two variations of the Flood it Problem, one is called Fixed Flood it and the other one Free Flood it. In the former, all the color assignments are made in the same monochromatic component. In the latter, it’s possible to choose a distinct monochromatic component for each movement. This paper presents a polynomial time solution for the Fixed Flood it Problem in circular-function graphs. The circular-function graphs are a new graph class defined for the first time in this work. Circular-function graphs are graphs which are intersection graphs of curves between two concentric circles, where each vertex is represented by a curve, and two vertex are neighbors if and only if their corresponding curves intersect each other. This graph class is a superclass of the co-comparability graphs, and the solution proposed in this paper is based on the solution of the Fixed Flood it Problem for co-comparability graphs, given by Fleischer and Woeginger in 2012. The solution of the Fixed Flood it Problem in circular-function graphs implies the solution to the same problem in circular trapezoid graphs, circular-arc graphs, circle graphs, circular permutation graphs, concave-round graphs, cycles, among others.