✦ LIBER ✦

Poset boxicity of graphs

✍ Scribed by W.T Trotter Jr.; Douglas B West

Publisher: Elsevier Science
Year: 1987
Tongue: English
Weight: 197 KB
Volume: 64
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(87)90247-0

No coin nor oath required. For personal study only.

✦ Synopsis

A t-box representation of a graph encodes each vertex as a box in t-space determined by the (integer) coordinates of its lower and upper corner, such that vertices are adjacent if and only if the corresponding boxes intersect. The boxicity of a graph G is the minirmlm t for which this can be done; equivalently, it is the minimum t such that G can be expressed as the intersection graph of intervals in the t-dimensional poset that is the product of t chains. Seheinerman defined the poset boxicity of a graph G to be the minimum t such that G is the intersection graph of intervals in some t-dimensional poset. In this paper, a special class of posets is used to show that the poset boxicity of a graph on n points is at most O(log log n). Furthermore, Ramsey's theorem is used to show the existence of graphs with arbitrarily large poset boxicity.

📜 SIMILAR VOLUMES

Boxicity of Circular Arc Graphs

✍ Diptendu Bhowmick; L. Sunil Chandran 📂 Article 📅 2010 🏛 Springer Japan 🌐 English ⚖ 352 KB

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

Chordal Bipartite Graphs with High Boxic

Chordal Bipartite Graphs with High Boxicity

✍ L. Sunil Chandran; Mathew C. Francis; Rogers Mathew 📂 Article 📅 2011 🏛 Springer Japan 🌐 English ⚖ 186 KB

Characterization of the graphs with boxi

Characterization of the graphs with boxicity ⩽2

✍ Martin Quest; Gerd Wegner 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 360 KB

The intersection graph of a family 8TI of sets has the sets in %' as vertices and an edge between two sets iff they have nonempty intersection. Following Roberts [4] the boxicity b(G) of a graph G is defined as the smallest d such that G is the intersection graph of boxes in Euclidean d-space, i.e.

Planar graphs and poset dimension

✍ Walter Schnyder 📂 Article 📅 1989 🏛 Springer Netherlands 🌐 English ⚖ 946 KB

M-chain graphs of posets

✍ Jenö Lehel; F.R. McMorris; Debra D. Scott 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 531 KB

The m-chain graph of a finite poset is defined as a generalization of the covering graph. 2-chain graphs of posets whose covering graphs are trees are characterized.