Graphs with E Edges Have Pagenumber O(√E)

✍ Scribed by S.M. Malitz

• Book ID: 102968496
• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 589 KB
• Volume: 17
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1994.1027

✦ 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. The main results of this paper: (1) any graph with (E) edges has pagenumber (O(\sqrt{E})); (2) there is a (d)-regular (N)-vertex graph with pagenumber (\Omega\left(\sqrt{d} N^{1 / 2-1 / d}\right)). The first bound is tight in the worst case; the second bound is tight when (d>\log N). Both results are dramatic improvements over previously known bounds. C 1994 Academic Press, Inc.