Abstract
We present two main results: a 2-page drawing and a rectilinear drawing of the n-dimensional cube Q n . Both drawings have the same number \(\frac{125}{768}4^n-\frac{2^{n-3}}{3}\left(3n^2+\frac{9+(-1)^{n+1}}{2}\right)\) of crossings, even though they are given by different constructions. The first improves the current best general 2-page drawing, while the second is the first non-trivial rectilinear drawing of Q n .
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ábrego, B., Aichholzer, O., Fernández-Merchant, S., Ramos, P., Salazar, G.: The 2-page crossing number of K n . In: Proc. 2012 Symposium on Computational Geometry, SoCG 2012, pp. 397–404. ACM (2012)
Balogh, J., Salazar, G.: k-sets, convex quadrilaterals, and the rectilinear crossing number of K n . Discrete Comput. Geom. 35(4), 671–690 (2006)
Buchheim, C., Zheng, L.: Fixed linear crossing minimization by reduction to the maximum cut problem. In: Chen, D.Z., Lee, D.T. (eds.) COCOON 2006. LNCS, vol. 4112, pp. 507–516. Springer, Heidelberg (2006)
Chung, F.R.K., Leighton, F.T., Rosenberg, A.L.: Embedding graphs in books: A layout problem with applications to VLSI design. SIAM J. Algebraic Discrete Methods 8, 33–58 (1987)
Dean, A.M., Richter, R.B.: The crossing number of C 4 ×C 4. J. Graph Theory 19, 125–129 (1995)
de Klerk, E., Pasechnik, D.: Improved lower bounds for the 2-page crossing numbers of K m,n and K n via semidefinite programming. SIAM J. Optim. 22(2), 581–595 (2012)
Erdős, P., Guy, R.K.: Crossing number problems. Amer. Math. Monthly 80, 52–58 (1973)
Faria, L., de Figueiredo, C.M.H., Sýkora, O., Vro, I.: An improved upper bound on the crossing number of the hypercube. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol. 2880, pp. 230–236. Springer, Heidelberg (2003)
Faria, L., de Figueiredo, C.M.H., Sýkora, O., Vrto, I.: An improved upper bound on the crossing number of the n-cube. J. Graph Theory 59, 145–161 (2008)
Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM J. Algebraic and Discrete Methods 4, 312–316 (1983)
Madej, T.: Bounds for the crossing number of the n-cube. J. Graph Theory 15, 81–97 (1991)
Masuda, S., Nakajima, K., Kashiwabara, T., Fujisawa, T.: Crossing minimization in linear embeddings of graphs. IEEE Trans. Comput. 39(1), 124–127 (1990)
Yannakakis, M.: Embedding planar graphs in four pages. In: 18th Annual ACM Symposium on Theory of Computing, Berkeley, CA (1986), J. Comput. System Sci. 38(1), 36–67 (1989)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Faria, L., de Figueiredo, C.M.H., Richter, R.B., vrt’o, I. (2013). The Same Upper Bound for Both: The 2-Page and the Rectilinear Crossing Numbers of the n-Cube. In: Brandstädt, A., Jansen, K., Reischuk, R. (eds) Graph-Theoretic Concepts in Computer Science. WG 2013. Lecture Notes in Computer Science, vol 8165. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45043-3_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-45043-3_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45042-6
Online ISBN: 978-3-642-45043-3
eBook Packages: Computer ScienceComputer Science (R0)