Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph. (English) Zbl 0933.05042
A topological book imbedding of a graph places the vertices along the spine and the edges in the pages; edges are allowed to cross the spine. Enomoto and Miyauchi (preprint) showed that every graph of order \(n\) and size \(m\) can be imbedded into a 3-page book with at most \(O(m\log n)\) edge-crossings over the spine. The present paper gives lower bounds on the number of edge-crossings over the spine which show that the bound \(O(m\log n)\) is essentially best possible.
Reviewer: Arthur T.White (Kalamazoo)
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C35 | Extremal problems in graph theory |
References:
| [2] | Bernhart, F.; Kainen, P. C., The book thickness of a graph, J. Combin. Theory Ser. B, 27, 320-331 (1979) · Zbl 0427.05028 |
| [3] | Chung, F. R.K.; Leighton, F. T.; Rosenberg, A. L., Embedding graphs in books: A layout problem with applications to VLSI design, SIAM J. Algebra Discrete Meth., 8, 33-58 (1987) · Zbl 0617.68062 |
| [5] | Enomoto, H.; Nakamigawa, T.; Ota, K., On the pagenumber of complete bipartite graphs, J. Combin. Theory Ser. B, 71, 111-120 (1997) · Zbl 0902.05019 |
| [6] | Miyauchi, M. S., An O(mn) algorithm for embedding graphs into 3-page book, Trans. of IEICE E77-A, 3, 521-526 (1994) |
| [8] | Muder, D. J.; Weaver, M. L.; West, D. B., Pagenumber of complete bipartite graphs, J. Graph Theory, 12, 469-489 (1988) · Zbl 0662.05020 |
| [9] | Yannakakis, M., Embedding planar graphs in four pages, J. Comput. System Sci., 38, 36-67 (1989) · Zbl 0673.05022 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
