Floor-Planning via Orderly Spanning Trees View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2002-02-21

AUTHORS

Liao Chien-Chih , Hsueh I. Lu , Yen Hsu-Chun

ABSTRACT

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} \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... »

PAGES

367-377

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-45848-4_29

DOI

http://dx.doi.org/10.1007/3-540-45848-4_29

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1012239146


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

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

HOW TO GET THIS DATA PROGRAMMATICALLY:

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

Subject Predicate Object
1 sg:pub.10.1007/3-540-45848-4_29 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N7d52cb621bb94439b7d7791c813cf97e
4 schema:datePublished 2002-02-21
5 schema:datePublishedReg 2002-02-21
6 schema: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} \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}.
7 schema:editor N07fa4c0d297546fc88a77def9084d8cd
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Na57ec06351324759ae2963e2ccc82307
12 schema:keywords VLSI chip design
13 ability
14 algorithm
15 area
16 aspects
17 chip design
18 comparison
19 concept
20 design
21 floor plan area
22 floor planning
23 fundamental step
24 important aspect
25 literature
26 module types
27 new algorithm
28 orderly spanning trees
29 plane triangulations
30 rectangle
31 rectangle of size
32 size
33 solution
34 spanning tree
35 step
36 time algorithm
37 trees
38 triangulation
39 types
40 schema:name Floor-Planning via Orderly Spanning Trees
41 schema:pagination 367-377
42 schema:productId N3b62294967f94008bb094bd798c16f0c
43 Nda5445badd1446049b4192b9522c75e3
44 schema:publisher N239611f9a7004f538a27220380c845a4
45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012239146
46 https://doi.org/10.1007/3-540-45848-4_29
47 schema:sdDatePublished 2022-05-10T10:36
48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
49 schema:sdPublisher N815a8175fb9142d0b0e54fa924b114ac
50 schema:url https://doi.org/10.1007/3-540-45848-4_29
51 sgo:license sg:explorer/license/
52 sgo:sdDataset chapters
53 rdf:type schema:Chapter
54 N000a287ef5684f7cb6a99061dc78897f schema:familyName Leipert
55 schema:givenName Sebastian
56 rdf:type schema:Person
57 N07fa4c0d297546fc88a77def9084d8cd rdf:first Ne61fa7a86fb44b6dadf3c045ee5c95e5
58 rdf:rest N9a295f1bd0774471a887d6be63db9620
59 N0d786beb1b7641f1be6bfd67dc7c3403 rdf:first sg:person.013345515575.46
60 rdf:rest N73b2fd357c5d4333a878659d2681498f
61 N136e58fc3f8545778f3a9e211bd8b43c schema:familyName Jünger
62 schema:givenName Michael
63 rdf:type schema:Person
64 N239611f9a7004f538a27220380c845a4 schema:name Springer Nature
65 rdf:type schema:Organisation
66 N3b62294967f94008bb094bd798c16f0c schema:name dimensions_id
67 schema:value pub.1012239146
68 rdf:type schema:PropertyValue
69 N73b2fd357c5d4333a878659d2681498f rdf:first sg:person.011206037075.06
70 rdf:rest rdf:nil
71 N7d52cb621bb94439b7d7791c813cf97e rdf:first Nb2a50b77206a4dd5a244690dac49054c
72 rdf:rest N0d786beb1b7641f1be6bfd67dc7c3403
73 N815a8175fb9142d0b0e54fa924b114ac schema:name Springer Nature - SN SciGraph project
74 rdf:type schema:Organization
75 N84c8aec653694cf18485eafc131c557a rdf:first N000a287ef5684f7cb6a99061dc78897f
76 rdf:rest rdf:nil
77 N9a295f1bd0774471a887d6be63db9620 rdf:first N136e58fc3f8545778f3a9e211bd8b43c
78 rdf:rest N84c8aec653694cf18485eafc131c557a
79 Na57ec06351324759ae2963e2ccc82307 schema:isbn 978-3-540-43309-5
80 978-3-540-45848-7
81 schema:name Graph Drawing
82 rdf:type schema:Book
83 Nb2a50b77206a4dd5a244690dac49054c schema:affiliation grid-institutes:grid.19188.39
84 schema:familyName Chien-Chih
85 schema:givenName Liao
86 rdf:type schema:Person
87 Nda5445badd1446049b4192b9522c75e3 schema:name doi
88 schema:value 10.1007/3-540-45848-4_29
89 rdf:type schema:PropertyValue
90 Ne61fa7a86fb44b6dadf3c045ee5c95e5 schema:familyName Mutzel
91 schema:givenName Petra
92 rdf:type schema:Person
93 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
94 schema:name Information and Computing Sciences
95 rdf:type schema:DefinedTerm
96 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
97 schema:name Artificial Intelligence and Image Processing
98 rdf:type schema:DefinedTerm
99 sg:person.011206037075.06 schema:affiliation grid-institutes:grid.19188.39
100 schema:familyName Hsu-Chun
101 schema:givenName Yen
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011206037075.06
103 rdf:type schema:Person
104 sg:person.013345515575.46 schema:affiliation grid-institutes:grid.28665.3f
105 schema:familyName Lu
106 schema:givenName Hsueh I.
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46
108 rdf:type schema:Person
109 grid-institutes:grid.19188.39 schema:alternateName Department of Electrical Engineering, National Taiwan University, 106, Taipei, Taiwan, Republic of China
110 Department of Electrical Engineering, National Taiwan University, Taipei 106, Taiwan, Republic of China
111 schema:name Department of Electrical Engineering, National Taiwan University, 106, Taipei, Taiwan, Republic of China
112 Department of Electrical Engineering, National Taiwan University, Taipei 106, Taiwan, Republic of China
113 rdf:type schema:Organization
114 grid-institutes:grid.28665.3f schema:alternateName Academia Sinica, Institute of Information Science, 115, Taipei, Taiwan, Republic of China
115 schema:name Academia Sinica, Institute of Information Science, 115, Taipei, Taiwan, Republic of China
116 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...