Subexponentialtime framework for optimal embeddings of graphs in integer lattices
(2004) 9th Scandinavian Workshop on Algorithm Theory In Algorithm Theory  SWAT 2004/Lecture Notes in Computer Science 3111. p.248259 Abstract
 We present a general framework for computing various optimal embeddings of undirected and directed connected graphs in two and multidimensional integer lattices in time subexponential 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 subexponential upper bounds in the two dimensional case and ddimensional case are respectively of the form 2(O(rootln log n)), 2(Orootlb log b)) and 2(n)(O(dl1/d) ((d1)/d)(log n)),2(O(dl l/d(d1)/d) (log b),) where l stands for the degree of the allowed overlap. For the problem of minimum total edge length planar or multidimensional 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 multidimensional integer lattices in time subexponential 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 subexponential upper bounds in the two dimensional case and ddimensional case are respectively of the form 2(O(rootln log n)), 2(Orootlb log b)) and 2(n)(O(dl1/d) ((d1)/d)(log n)),2(O(dl l/d(d1)/d) (log b),) where l stands for the degree of the allowed overlap. For the problem of minimum total edge length planar or multidimensional 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:
http://lup.lub.lu.se/record/272609
 author
 Dessmark, Anders ^{LU} ; Lingas, Andrzej ^{LU} and Lundell, EvaMarta ^{LU}
 organization
 publishing date
 2004
 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
 16113349
 03029743
 ISBN
 9783540223399
 DOI
 10.1007/b98413
 project
 VR 20024049
 language
 English
 LU publication?
 yes
 id
 46227d3a45554feb93a0df9b04a5fb60 (old id 272609)
 date added to LUP
 20071023 13:41:49
 date last changed
 20170101 04:55:22
@inproceedings{46227d3a45554feb93a0df9b04a5fb60, abstract = {We present a general framework for computing various optimal embeddings of undirected and directed connected graphs in two and multidimensional integer lattices in time subexponential 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 subexponential upper bounds in the two dimensional case and ddimensional case are respectively of the form 2(O(rootln log n)), 2(Orootlb log b)) and 2(n)(O(dl1/d) ((d1)/d)(log n)),2(O(dl l/d(d1)/d) (log b),) where l stands for the degree of the allowed overlap. For the problem of minimum total edge length planar or multidimensional 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, EvaMarta}, booktitle = {Algorithm Theory  SWAT 2004/Lecture Notes in Computer Science}, isbn = {9783540223399}, issn = {16113349}, language = {eng}, pages = {248259}, publisher = {Springer}, title = {Subexponentialtime framework for optimal embeddings of graphs in integer lattices}, url = {http://dx.doi.org/10.1007/b98413}, volume = {3111}, year = {2004}, }