## Abstract

We study powers of certain geometric intersection graphs: interval graphs, m-trapezoid graphs and circular-arc graphs. We define the pseudo-product, (G, G′) → G*G′, of two graphs G and G′ on the same set of vertices, and show that G*G′ is contained in one of the three classes of graphs mentioned here above, if both G and G′ are also in that class and fulfill certain conditions. This gives a new proof of the fact that these classes are closed under taking power; more importantly, we get efficient methods for computing the representation for G^{k} if k ≥ 1 is an integer and G belongs to one of these classes, with a given representation sorted by endpoints. We then use these results to give efficient algorithms for the k-independent set, dispersion and weighted dispersion problem on these classes of graphs, provided that their geometric representations are given.

Original language | English |
---|---|

Pages (from-to) | 3-16 |

Number of pages | 14 |

Journal | Discrete Applied Mathematics |

Volume | 132 |

Issue number | 1-3 |

DOIs | |

Publication status | Published - 15 Oct 2003 |

Event | Stability in Graphs and Related Topics - Lausanne, Switzerland Duration: 1 Jul 2002 → 1 Jul 2002 |

## Other keywords

- Circular-arc graphs
- Dispersion
- Intersection graphs
- Interval graphs
- Powers of graphs
- Trapezoid graphs