𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On intersection representations of co-planar graphs

✍ Scribed by Jan Kratochvíl; Aleš Kuběna

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
221 KB
Volume
178
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We show that complements of planar graphs have intersection representations by convex sets in the plane, i.e., for every planar graph, one can assign convex sets in the plane to its vertices in such a way that two of the sets are disjoint if and only if the correspondning vertices are adjacent. This fact has a complexity consequence --it follows that the problem of determining the clique number of an intersection graph of convex sets in the plane is NP-hard. We note that the complexity of this problem for intersection graphs of straight line segments in the plane is unknown. @ 1998 Elsevier Science Ltd.

📜 SIMILAR VOLUMES

On set intersection representations of g
On set intersection representations of graphs
✍ Stasys Jukna 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 193 KB 👁 1 views

## Abstract The intersection dimension of a bipartite graph with respect to a type __L__ is the smallest number __t__ for which it is possible to assign sets __A__~__x__~⊆{1, …, __t__} of labels to vertices __x__ so that any two vertices __x__ and __y__ from different parts are adjacent if and only

On planar intersection graphs with forbi
On planar intersection graphs with forbidden subgraphs
✍ János Pach; Micha Sharir 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB

## Abstract Let ${\cal C}$ be a family of __n__ compact connected sets in the plane, whose intersection graph $G({\cal C})$ has no complete bipartite subgraph with __k__ vertices in each of its classes. Then $G({\cal C})$ has at most __n__ times a polylogarithmic number of edges, where the exponent

Simultaneous intersection representation
Simultaneous intersection representation of pairs of graphs
✍ Tanenbaum, Paul J. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 436 KB 👁 2 views

We characterize the pairs (G 1 , G 2 ) of graphs on a shared vertex set that are intersection polysemic: those for which the vertices may be assigned subsets of a universal set such that G 1 is the intersection graph of the subsets and G 2 is the intersection graph of their complements. We also cons

Intersection Representation of Complete
Intersection Representation of Complete Unbalanced Bipartite Graphs
✍ Nancy Eaton 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 282 KB

A p-intersection representation of a graph G is a map, f, that assigns each vertex a subset of [1, 2, ..., t] The symbol % p (G) denotes this minimum t such that a p-intersection representation of G exists. In 1966 Erdo s, Goodman, and Po sa showed that for all graphs G on 2n vertices, % 1 (G) % 1

Rectangular and visibility representatio
Rectangular and visibility representations of infinite planar graphs
✍ Carsten Thomassen 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 75 KB

## Abstract We provide a new method for extending results on finite planar graphs to the infinite case. Thus a result of Ungar on finite graphs has the following extension: Every infinite, planar, cubic, cyclically 4‐edge‐connected graph has a representation in the plane such that every edge is a h