𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Grid intersection graphs and boxicity

✍ Scribed by S. Bellantoni; I. Ben-Arroyo Hartman; T. Przytycka; S. Whitesides

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
558 KB
Volume
114
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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 of k-dimensional boxes (parallel to the coordinate axis) in a (k+ I)-dimensional space. We prove that all bipartite graphs with boxicity two. have grid dimensions one, that is, they can be represented as intersection graphs of horizontal and vertical intervals in the plane. We also introduce some inequalities for the grid dimension of a graph, and discuss extremal graphs with large grid dimensions.

πŸ“œ SIMILAR VOLUMES

On grid intersection graphs
On grid intersection graphs
✍ I.Ben-Arroyo Hartman; Ilan Newman; Ran Ziv πŸ“‚ Article πŸ“… 1991 πŸ› Elsevier Science 🌐 English βš– 759 KB

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 segm

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

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

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