𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Boxicity of Graphs on Surfaces

✍ Scribed by Louis Esperet, Gwenaël Joret

Book ID
120788681
Publisher
Springer Japan
Year
2012
Tongue
English
Weight
223 KB
Volume
29
Category
Article
ISSN
0911-0119

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Boxicity of line graphs
Boxicity of line graphs
✍ L. Sunil Chandran; Rogers Mathew; Naveen Sivadasan 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 263 KB
Poset boxicity of graphs
Poset boxicity of graphs
✍ W.T Trotter Jr.; Douglas B West 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 197 KB

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; e

Boxicity of Circular Arc Graphs
Boxicity of Circular Arc Graphs
✍ Diptendu Bhowmick; L. Sunil Chandran 📂 Article 📅 2010 🏛 Springer Japan 🌐 English ⚖ 352 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.

Decomposition of Graphs on Surfaces
Decomposition of Graphs on Surfaces
✍ Maurits de Graaf; Alexander Schrijver 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 266 KB

dedicated to professor w. t. tutte on the occasion of his eightieth birthday Let G=(V, E) be an Eulerian graph embedded on a triangulizable surface S. We show that E can be decomposed into closed curves C 1 , ..., C k such that mincr(G, D)= k i=1 mincr(C i , D) for each closed curve D on S. Here min