Topological graph theory comprises a large number of topics which have the common elements of points, lines, and patches sitting in an ambient space of three or four dimensions.
As time permits, this page will sketch a few areas and give pointers to the literature.
Standard References:
A book consists of the union of a finite number of closed half-spaces, all sharing the same boundary line (called the spine of the book); the half-spaces are called the pages. Thus, books are a type of pseudo-manifold; that is, they are locally Euclidean except for certain points which have neighborhoods consisting of disks with possible singularities. Atneosen's thesis showed that every finite graph can be embedded in a book with 3 pages.
The notion of embedding in a book was extended by Loyal Taylor Ollman and myself. We discussed the idea during our final year as grad students together at Cornell during the Spring of 1970.
Either through misunderstanding the original idea or because we found our version more interesting, Taylor and I considered [LTO73], [PCK74, p. 97] the added requirement that each edge lies within a single page. Ollman noted that then n/2 (rounded up) pages are needed for K_n while I observed that 1- and 2-page graphs can be characterized as outerplanar or subhamiltonian, resp. Bernhart and Kainen [BK79] found bounds on the book thickness, or page number as it is now often called, and we showed that the book thickness of the $d$-hypercube is at most $d-1$. So while the Atneosen definition of book thickness does not exceed 3, the more restricted type of embedding has a more complex answer. MOreover, this latter type of embedding of graphs in books has applications in computer science, vehicle traffic flow, and molecular biology; see [DMW04], [PCK90], and [GS99], resp.
Independently, book thickness arose in some special situations in computer science - see [EI71], [RT72]
In A. T. White's new book, Graphs of groups on surfaces: p. 103 last para and thm. 8-34 on the next page:
The result achieved by Borodin and Melnikov [BM2] was also achieved by Kainen [Thm. 6.5 and 6.7, p. 99, ref. PCK74].
[PCK74] is an early survey of topological graph theory, which among other topics, includes a survey of the connection with piecewise-linear topology. Also, it mentions that the notion of a pseudo-manifold (see, e.g., Spanier) is equivalent to having a pinched surface.
On crossing numbers of cartesian products of graphs with hypercubes, White cites a joint paper of ours but see also PCK, On the stable crossing number of cubes, Proc. AMS 36 (1972) 55--62.)
refs:
LTO73: L. T. Ollman, Book-thickness of graphs, in Proc. 4th SE Conf. on Graph Theory, Combinatorics and Computing, Util. Math, Winnipeg, 1973, p. 459 (abstract only). PCK74: P. C. Kainen, Some recent results in topological graph theory, in Graphs and Combinatorics (Bari and Harary, Eds.), pp. 76--108. BK79: F. Bernhart and P. C. Kainen, On the book thickness of a graph, J. Combin. Theory 27B (1979) 320--331. PCK90: P. C. Kainen, Book thickness of graphs, II, Util. Math., 1990 (proc. of 20th SE Conf., Boca Raton). GS99: P. M. Gleiss, P. F. Stadler. Relevant cycles in biopolymers and random graphs, 4th Slovene Conference on Graph Theory, Bled, June 28-July 2, 1999 DMW04: V. Dujmovic, P. Morin, and D. R. Wood, Layout of graphs with bounded tree-width, arXiv xxx.sf.nchc.gov.tw/pdf/cs.DM/0406024; also see arXiv:math.CO/0503553 v1 24 Mar 2005 [RT72] R. TARJAN, Sorting using networks of queues and stacks. J. Assoc. Comput. Mach., 19:341--346, 1972. [EI71] S. EVEN AND A. ITAI, Queues, stacks, and graphs. In Z. KOHAVI AND A. PAZ, eds., Proc. International Symp. on Theory of Machines and Computations, pp. 71--86, Academic Press, 1971.
1/8/06 Back to the index page page.