Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Drawing a Graph in a Hypercube. | Drawing a Graph in a Hypercube David R. Wood Departament de Matemàtica Aplicada II Universitat Politecnica de Catalunya Barcelona Spain Submitted Nov 16 2004 Accepted Aug 11 2006 Published Aug 22 2006 Mathematics Subject Classification 05C62 graph representations 05C78 graph labelling 11B83 number theory special sequences Abstract A d-dimensional hypercube drawing of a graph represents the vertices by distinct points in 0 1 d such that the line-segments representing the edges do not cross. We study lower and upper bounds on the minimum number of dimensions in hypercube drawing of a given graph. This parameter turns out to be related to Sidon sets and antimagic injections. 1 Introduction Two-dimensional graph drawing 5 15 and to a lesser extent three-dimensional graph drawing 6 17 27 have been widely studied in recent years. Much less is known about graph drawing in higher dimensions. For research in this direction see references 3 8 9 26 27 . This paper studies drawings of graphs in which the vertices are positioned at the points of a hypercube. We consider undirected finite and simple graphs G with vertex set V G and edge set E G . Consider an injection A V G 0 1 d. For each edge vw 2 E G let A vw be the open line-segment with endpoints A v and A w . Two distinct edges vw xy 2 E G cross if A vw n A xy 0. We say A is a d-dimensional hypercube drawing of G if no two edges of G cross. A d-dimensional hypercube drawing is said to have volume 2d. That Supported by a Marie Curie Fellowship of the European Community under contract 023865 and by projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2001SGR00224. Research initiated in the Department of Applied Mathematics and the Institute for Theoretical Computer Science at Charles University Prague Czech Republic. Supported by project LN00A056 of the Ministry of Education of the Czech Republic and by the European Union Research Training Network COMBSTRU. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R73 1 .
