NDLI: Many to One Embeddings from Grids into Cylinders, Tori, and Hypercubes

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Chow, Stirling Manke, Dennis Ellis, John
Copyright Year	2003
Abstract	We describe novel methods for embedding 2-dimensional grid graphs into cylinders (one way wrap-around grids), tori, and hypercubes, where the guest grid G is larger than the host graph H, implying a many to one embedding.We call $\lceil\mid G\mid / \mid H\mid\rceil$ the optimal load, denoted l. We consider optimal embeddings with respect to dilation (the stretching of guest edges) and load; i.e., edges are mapped to edges or onto one node, and the number of grid nodes mapped onto any hypercube node is not greater than l.We show, by construction, that, for loads of at least 4, optimal embeddings into the hypercube always exist subject only to modest restrictions on the relative dimensions of guest and host. If the problem instances are grouped by grid height, the restrictions imply that only some finite number of instances in each group may not be solvable by the given methods.The essence of the method is a mapping from grids into cylinders of height at least one half of but not greater than the grid height, and so it can also be used to construct embeddings into cylinders and tori.Previous work has gone so far as to show that if the optimal load l is a power of 2, then dilation 1, load l+1 embeddings into the hypercube can be constructed. Optimal results for loads 2 and 3 are not known.
Starting Page	386
Ending Page	407
Page Count	22
File Format	PDF
ISSN	00975397
DOI	10.1137/S0097539700377657
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	2
Volume Number	32
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2003-01-01
Access Restriction	Subscribed
Subject Keyword	Planar graphs; geometric and topological aspects of graph theory hypercube torus grid graph embedding cylinder many to one
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Embedding of Grids into Optimal Hypercubes

Dynamic Tree Embeddings in Butterflies and Hypercubes

Re-embeddings of Maximum 1-Planar Graphs

Book Embedding of Toroidal Bipartite Graphs

Exponentially many maximum genus embeddings and genus embeddings for complete graphs

On Relaxed Squashed Embedding of Graphs into a Hypercube

Optimal Parallel Algorithms for Straight-Line Grid Embeddings of Planar Graphs

Embedding 2-dimensional grids into optimal hypercubes with edge-congestion 1 or 2 (1998).

Embedding 2-Dimensional Grids Into Optimal Hypercubes With Edge-Congestion 1 Or 2 (1998)

Many to One Embeddings from Grids into Cylinders, Tori, and Hypercubes

Similar Documents

Embedding of Grids into Optimal Hypercubes

Dynamic Tree Embeddings in Butterflies and Hypercubes

Re-embeddings of Maximum 1-Planar Graphs

Book Embedding of Toroidal Bipartite Graphs

Exponentially many maximum genus embeddings and genus embeddings for complete graphs

On Relaxed Squashed Embedding of Graphs into a Hypercube

Optimal Parallel Algorithms for Straight-Line Grid Embeddings of Planar Graphs

Embedding 2-dimensional grids into optimal hypercubes with edge-congestion 1 or 2 (1998).

Embedding 2-Dimensional Grids Into Optimal Hypercubes With Edge-Congestion 1 Or 2 (1998)

Many to One Embeddings from Grids into Cylinders, Tori, and Hypercubes