Advanced

Subexponential-time framework for optimal embeddings of graphs in integer lattices

Dessmark, Anders LU ; Lingas, Andrzej LU and Lundell, Eva-Marta LU (2004) 9th Scandinavian Workshop on Algorithm Theory In Algorithm Theory - SWAT 2004/Lecture Notes in Computer Science 3111. p.248-259
Abstract
We present a general framework for computing various optimal embeddings of undirected and directed connected graphs in two and multi-dimensional integer lattices in time sub-exponential either in the minimum number n of lattice points used by such optimal embeddings or in the budget upper bound b on the number of lattice points that may be used in an embedding. The sub-exponential upper bounds in the two dimensional case and d-dimensional case are respectively of the form 2(O(rootln log n)), 2(Orootlb log b)) and 2(n)(O(dl1/d) ((d-1)/d)(log n)),2(O(dl l/d(d-1)/d) (log b),) where l stands for the degree of the allowed overlap. For the problem of minimum total edge length planar or multi-dimensional embedding or layout of a graph and the... (More)
We present a general framework for computing various optimal embeddings of undirected and directed connected graphs in two and multi-dimensional integer lattices in time sub-exponential either in the minimum number n of lattice points used by such optimal embeddings or in the budget upper bound b on the number of lattice points that may be used in an embedding. The sub-exponential upper bounds in the two dimensional case and d-dimensional case are respectively of the form 2(O(rootln log n)), 2(Orootlb log b)) and 2(n)(O(dl1/d) ((d-1)/d)(log n)),2(O(dl l/d(d-1)/d) (log b),) where l stands for the degree of the allowed overlap. For the problem of minimum total edge length planar or multi-dimensional embedding or layout of a graph and the problem of an optimal protein folding in the so called HP model we obtain the upper bounds in terms of n. Note that in case of protein folding n is also the size of the input. The list of problems for which we can derive the upper bounds in terms of b includes among other things: 1. a minimum area planar embedding or layout of a graph, 2. a minimum bend planar or three dimensional embedding or layout, 3. a minimum maximum edge length planar or three dimensional embedding or layout. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Algorithm Theory - SWAT 2004/Lecture Notes in Computer Science
volume
3111
pages
248 - 259
publisher
Springer
conference name
9th Scandinavian Workshop on Algorithm Theory
external identifiers
  • wos:000222682500022
  • scopus:35048818561
ISSN
1611-3349
0302-9743
ISBN
978-3-540-22339-9
DOI
10.1007/b98413
project
VR 2002-4049
language
English
LU publication?
yes
id
46227d3a-4555-4feb-93a0-df9b04a5fb60 (old id 272609)
date added to LUP
2007-10-23 13:41:49
date last changed
2017-01-01 04:55:22
@inproceedings{46227d3a-4555-4feb-93a0-df9b04a5fb60,
  abstract     = {We present a general framework for computing various optimal embeddings of undirected and directed connected graphs in two and multi-dimensional integer lattices in time sub-exponential either in the minimum number n of lattice points used by such optimal embeddings or in the budget upper bound b on the number of lattice points that may be used in an embedding. The sub-exponential upper bounds in the two dimensional case and d-dimensional case are respectively of the form 2(O(rootln log n)), 2(Orootlb log b)) and 2(n)(O(dl1/d) ((d-1)/d)(log n)),2(O(dl l/d(d-1)/d) (log b),) where l stands for the degree of the allowed overlap. For the problem of minimum total edge length planar or multi-dimensional embedding or layout of a graph and the problem of an optimal protein folding in the so called HP model we obtain the upper bounds in terms of n. Note that in case of protein folding n is also the size of the input. The list of problems for which we can derive the upper bounds in terms of b includes among other things: 1. a minimum area planar embedding or layout of a graph, 2. a minimum bend planar or three dimensional embedding or layout, 3. a minimum maximum edge length planar or three dimensional embedding or layout.},
  author       = {Dessmark, Anders and Lingas, Andrzej and Lundell, Eva-Marta},
  booktitle    = {Algorithm Theory - SWAT 2004/Lecture Notes in Computer Science},
  isbn         = {978-3-540-22339-9},
  issn         = {1611-3349},
  language     = {eng},
  pages        = {248--259},
  publisher    = {Springer},
  title        = {Subexponential-time framework for optimal embeddings of graphs in integer lattices},
  url          = {http://dx.doi.org/10.1007/b98413},
  volume       = {3111},
  year         = {2004},
}