On the Genus of Pancake Network

On the Genus of Pancake Network

Quan Nguyen1 and Saïd Bettayeb2  ‎
‎1University of Texas at Dallas, Richardson, USA‎
‎2University of Houston at Clear Lake, Houston, USA‎



Abstract: Both the pancake graph and star graph are Cayley graphs and are especially attractive for parallel processing. They both ‎have sublogarithmic diameter, and are fairly sparse compared to hypercubes.  In this paper, we focus on another important ‎property, namely the genus.  The genus of a graph is the minimum number of handles needed for drawing the graph on the ‎plane without edges crossing.  We will investigate the upper bound and lower bound for the genus of pancake graph and ‎compare these values with the genus of the star graph as well as that of the hypercube. ‎

Keywords: Genus, binary hypercube, permutation, pancake network, cayley graph, and prefix reversal.‎
 

Received April 28, 2009; accepted November 5, 2009‎

Full Text
Read 3148 times Last modified on Thursday, 23 June 2011 05:13
Share
Top
We use cookies to improve our website. By continuing to use this website, you are giving consent to cookies being used. More details…