𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Powers of geometric intersection graphs and dispersion algorithms

✍ Scribed by Geir Agnarsson; Peter Damaschke; Magnús M. Halldórsson

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
188 KB
Volume
132
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

We study powers of certain geometric intersection graphs: interval graphs, m-trapezoid graphs and circular-arc graphs. We deÿne 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 fulÿll certain conditions. This gives a new proof of the fact that these classes are closed under taking power; more importantly, we get e cient 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 e cient algorithms for the k-independent set, dispersion and weighted dispersion problem on these classes of graphs, provided that their geometric representations are given.

📜 SIMILAR VOLUMES

On the intersection of edges of a geomet
On the intersection of edges of a geometric graph by straight lines
✍ N. Alon; M.A. Perles 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 969 KB

A geometric graph ( = gg) is a pair G = (V, E), where V is a finite set of points ( = vertices) in general position in the plane, and E is a set of open straight line segments ( = edges) whose endpoints are in V. G is a convex gg ( = egg) if V is the set of vertices of a convex polygon. For n 3 1, 0

Intersection number and capacities of gr
Intersection number and capacities of graphs
✍ J. Körner 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 955 KB

For an arbitrary graph G we determine the asymptotics of the intersection number (edgeclique covering number) of the categorical (or weak) product of G and the complete graph K,, asymptotically in n. The result follows from a more general theorem on graph capacities which generalizes an earlier resu

Distinguishing Cartesian powers of graph
Distinguishing Cartesian powers of graphs
✍ Wilfried Imrich; Sandi Klavžar 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 132 KB

The distinguishing number D(G) of a graph is the least integer d such that there is a d-labeling of the vertices of G that is not preserved by any nontrivial automorphism of G. We show that the distinguishing number of the square and higher powers of a connected graph G = K 2 , K 3 with respect to t