Lower Bounds on the mim-width of Some Graph Classes

Stefan Mengel

mim-width is a recent graph width measure that has seen applications in graph algorithms and problems related to propositional satisfiability. In this paper, we show linear lower b…