Ontology type: schema:Chapter Open Access: True
2002-02-21
AUTHORSLiao Chien-Chih , Hsueh I. Lu , Yen Hsu-Chun
ABSTRACTFloor-planning is a fundamental step in VLSI chip design. Based upon the concept of orderly spanning trees, we present a simple O(n)-time algorithm to construct a floor-plan for any n-node plane triangulation. In comparison with previous floor-planning algorithms in the literature, our solution is not only simpler in the algorithm itself, but also produces floor-plans which require fewer module types. An equally important aspect of our new algorithm lies in its ability to fit the floor-plan area in a rectangle of size \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ (n - 1) \times \left\lfloor {\frac{{2n + 1}} {3}} \right\rfloor $$\end{document}. More... »
PAGES367-377
Graph Drawing
ISBN
978-3-540-43309-5
978-3-540-45848-7
http://scigraph.springernature.com/pub.10.1007/3-540-45848-4_29
DOIhttp://dx.doi.org/10.1007/3-540-45848-4_29
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1012239146
JSON-LD is the canonical representation for SciGraph data.
TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT
[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
"about": [
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Artificial Intelligence and Image Processing",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Department of Electrical Engineering, National Taiwan University, Taipei 106, Taiwan, Republic of China",
"id": "http://www.grid.ac/institutes/grid.19188.39",
"name": [
"Department of Electrical Engineering, National Taiwan University, Taipei 106, Taiwan, Republic of China"
],
"type": "Organization"
},
"familyName": "Chien-Chih",
"givenName": "Liao",
"type": "Person"
},
{
"affiliation": {
"alternateName": "Academia Sinica, Institute of Information Science, 115, Taipei, Taiwan, Republic of China",
"id": "http://www.grid.ac/institutes/grid.28665.3f",
"name": [
"Academia Sinica, Institute of Information Science, 115, Taipei, Taiwan, Republic of China"
],
"type": "Organization"
},
"familyName": "Lu",
"givenName": "Hsueh I.",
"id": "sg:person.013345515575.46",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Electrical Engineering, National Taiwan University, 106, Taipei, Taiwan, Republic of China",
"id": "http://www.grid.ac/institutes/grid.19188.39",
"name": [
"Department of Electrical Engineering, National Taiwan University, 106, Taipei, Taiwan, Republic of China"
],
"type": "Organization"
},
"familyName": "Hsu-Chun",
"givenName": "Yen",
"id": "sg:person.011206037075.06",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011206037075.06"
],
"type": "Person"
}
],
"datePublished": "2002-02-21",
"datePublishedReg": "2002-02-21",
"description": "Floor-planning is a fundamental step in VLSI chip design. Based upon the concept of orderly spanning trees, we present a simple O(n)-time algorithm to construct a floor-plan for any n-node plane triangulation. In comparison with previous floor-planning algorithms in the literature, our solution is not only simpler in the algorithm itself, but also produces floor-plans which require fewer module types. An equally important aspect of our new algorithm lies in its ability to fit the floor-plan area in a rectangle of size \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\n(n - 1) \\times \\left\\lfloor {\\frac{{2n + 1}}\n{3}} \\right\\rfloor $$\\end{document}.",
"editor": [
{
"familyName": "Mutzel",
"givenName": "Petra",
"type": "Person"
},
{
"familyName": "J\u00fcnger",
"givenName": "Michael",
"type": "Person"
},
{
"familyName": "Leipert",
"givenName": "Sebastian",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/3-540-45848-4_29",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-540-43309-5",
"978-3-540-45848-7"
],
"name": "Graph Drawing",
"type": "Book"
},
"keywords": [
"orderly spanning trees",
"spanning tree",
"floor planning",
"time algorithm",
"algorithm",
"plane triangulations",
"module types",
"new algorithm",
"rectangle of size",
"chip design",
"fundamental step",
"VLSI chip design",
"design",
"concept",
"triangulation",
"solution",
"important aspect",
"floor plan area",
"rectangle",
"step",
"trees",
"aspects",
"area",
"comparison",
"literature",
"types",
"size",
"ability"
],
"name": "Floor-Planning via Orderly Spanning Trees",
"pagination": "367-377",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1012239146"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/3-540-45848-4_29"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/3-540-45848-4_29",
"https://app.dimensions.ai/details/publication/pub.1012239146"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-10T10:36",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_105.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/3-540-45848-4_29"
}
]
Download the RDF metadata as: json-ld nt turtle xml License info
JSON-LD is a popular format for linked data which is fully compatible with JSON.
curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/3-540-45848-4_29'
N-Triples is a line-based linked data format ideal for batch operations.
curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/3-540-45848-4_29'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-45848-4_29'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-45848-4_29'
This table displays all metadata directly associated to this object as RDF triples.
116 TRIPLES
23 PREDICATES
53 URIs
46 LITERALS
7 BLANK NODES