×

Minimal embedding of hypercubic graphs on surface. (English) Zbl 1349.57002

Akiyama, Jin (ed.) et al., Computational geometry, graphs and applications. 9th international conference, CGGA 2010, Dalian, China, November 3–6, 2010. Revised selected papers. Berlin: Springer (ISBN 978-3-642-24982-2/pbk). Lecture Notes in Computer Science 7033, 122-129 (2011).
Summary: In this paper, we propose a minimal embedding of a non-planar, \(n\)-dimensional hypercubic graph on a surface as a “standard” embedding. The “standard” form of embedding graph on a surface has been understudied and therefore, has remained undefined. The aim of this paper is to define what the “standard form” is for a non-planar graph, while distinguishing different embedding patterns of a graph. As a result, we defined a value \(\omega (G)\) for all non-planar graphs \(G\), and determined the value \(\omega (Q _{n })\) for \(n\)-dimensional hypercubic graphs denoted by \(Q _{n }\).
For the entire collection see [Zbl 1225.68007].

MSC:

57M15 Relations of low-dimensional topology with graph theory
PDFBibTeX XMLCite
Full Text: DOI