| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 419310 | Discrete Applied Mathematics | 2015 | 30 Pages |
Abstract
Bubble models are 2-dimensional representations of proper interval graphs. We consider proper interval graphs that have bubble models of specific properties. We characterise the maximal such proper interval graphs of bounded clique-width and of bounded linear clique-width and the minimal such proper interval graphs whose clique-width and linear clique-width exceed the bounds. As a consequence, we can efficiently compute the clique-width and linear clique-width of the considered graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Daniel Meister, Udi Rotics,