Imbalance parameterized by twin cover revisited

Abstract

Imbalance is a classical graph layout problem with several applications, particularly in graph drawing. The imbalance of a layout σ is determined by how well-balanced the neighbors of the vertices are in σ. In the present work, we study the problem of Imbalance parameterized by the twin cover of a graph. We show that Imbalance is XP parameterized by twin cover, and FPT when parameterized by the twin cover and the size of the largest clique outside the twin cover. In contrast, we introduce a notion of succinct representations of graphs in terms of their twin cover and demonstrate that Imbalance is NP-hard in the setting of succinct representations, even for graphs that have a twin cover of size one.