𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Genus g Graphs Have Pagenumber O(√g)

✍ Scribed by S.M. Malitz

Book ID
102968497
Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
916 KB
Volume
17
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

A book embedding of a graph consists of a linear ordering of the vertices along the spine of a book and an assignment of edges to pages so that edges residing on the same page do not intersect. The minimum number of pages in which a graph can be embedded is its pagenumber. We verify a conjecture due to Heath and Istrail which asserts that any graph of genus (g) has pagenumber (O(\sqrt{g})). This bound is optimal in the worst case. A randomized algorithm to embed a genus (g) graph in (O(\sqrt{g})) pages is presented. 1994 Academic Press, Inc.

📜 SIMILAR VOLUMES

Graphs with E Edges Have Pagenumber O(√E
Graphs with E Edges Have Pagenumber O(√E)
✍ S.M. Malitz 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 589 KB

A book embedding of a graph consists of a linear ordering of the vertices along the spine of a book and an assignment of edges to pages so that edges residing on the same page do not intersect. The minimum number of pages in which a graph can be embedded is its pagenumber. The main results of this p

Sufficient conditions for graphs to have
Sufficient conditions for graphs to have (g, f)-factors
✍ Yoshimi Egawa; Mikio Kano 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 170 KB

We give sufficient conditions for a graph to have a (g,f)-factor. For example, we prove that a graph G has a (g,f)-factor if g(v) < f(v) for all vertices v of G and g(x)/deg~(x) <~ f(y)/deg~(y) for all adjacent vertices x and y of G.

A Characterization of Graphs Having All
A Characterization of Graphs Having All (g, f)-Factors
✍ Thomas Niessen 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 310 KB

Let G be a graph with vertex set V and let g, f : V Ä Z + . We say that G has all ( g, f )-factors if G has an h-factor for every h: V Ä Z + such that g(v) h(v) f (v) for every v # V and at least one such h exists. In this note, we derive from Tutte's f-factor theorem a similar characterization for