✦ LIBER ✦

On grid intersection graphs

✍ Scribed by I.Ben-Arroyo Hartman; Ilan Newman; Ran Ziv

Publisher: Elsevier Science
Year: 1991
Tongue: English
Weight: 759 KB
Volume: 87
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(91)90069-e

No coin nor oath required. For personal study only.

✦ Synopsis

Hartman I.B.-A., I. Newman and R. Ziv, On grid intersection graphs, Discrete Mathematics 87 (1991) 41-52. A bipartite graph G = (X, Y; E) has a grid representation if X and Y correspond to sets of horizontal and vertical segments in the plane, respectively, such that (xi, y,) E E if and only if segments

x, and y, intersect.

We prove that all planar bipartite graphs have a grid representation, and exhibit some infinite families of graphs with no grid representation-among them the point line incidence graph of projective planes.

* The research was done while the author was in the Mathematics Department,

📜 SIMILAR VOLUMES

Grid intersection graphs and boxicity

✍ S. Bellantoni; I. Ben-Arroyo Hartman; T. Przytycka; S. Whitesides 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 558 KB

A graph has hyuiciry k if k is the smallest integer such that G is an intersection graph of k-dimensional boxes in a &-dimensional space (where the sides of the boxes are parallel to the coordinate axis). A graph has grid dimension k if k is the smallest integer such that G is an intersection graph

Edge intersection graphs of single bend

Edge intersection graphs of single bend paths on a grid

✍ Martin Charles Golumbic; Marina Lipshteyn; Michal Stern 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 195 KB

Intersections of longest cycles in grid

Intersections of longest cycles in grid graphs

✍ Menke, B.; Zamfirescu, T.; Zamfirescu, C. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 292 KB 👁 3 views

It is well-known that the largest cycles of a graph may have empty intersection. This is the case, for example, for any hypohamiltonian graph. In the literature, several important classes of graphs have been shown to contain examples with the above property. This paper investigates a (nontrivial) cl

General results on tolerance intersectio

General results on tolerance intersection graphs

✍ M. S. Jacobson; F. R. McMorris; E. R. Scheinerman 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 255 KB 👁 1 views

## Abstract In this paper, general results are presented that are related to ϕ‐tolerance intersection graphs previously defined by Jacobson, McMorris, and Mulder. For example, it is shown that all graphs are ϕ‐tolerance intersection graphs for all ϕ, yet for “nice” ϕ, almost no graphs are ϕ‐toleran

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