You are here:   
  1. Home
  2. Articles
  3. http://scigraph.springernature.com/pub.10.1007/s10878-010-9324-8

Improved floor-planning of graphs via adjacency-preserving transformations View Full Text

Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2010-04-24

AUTHORS

Huaming Zhang, Sadish Sadasivam

ABSTRACT

Let G=(V,E) and G′=(V′,E′) be two graphs, an adjacency-preserving transformation from G to G′ is a one-to-many and onto mapping from V to V′ satisfying the following: (1) Each vertex v∈V in G is mapped to a non-empty subset \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}(v)\subset V'$\end{document} in G′. The subgraph induced by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}(v)$\end{document} is a connected subgraph of G′; (2) if u≠v∈V, then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}(u)\cap\mathcal{A}(v)=\emptyset$\end{document}; and (3) two vertices u and v are adjacent to each other in G if and only if subgraphs induced by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}(u)$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}(v)$\end{document} are connected in G′.In this paper, we study adjacency-preserving transformations from plane triangulations to irreducible triangulations (which are internally triangulated, with four exterior vertices and no separating triangles). As one shall see, our transformations not only preserve adjacency well, but also preserve the endowed realizers of plane triangulations well in the endowed transversal structures of the image irreducible triangulations, which may be desirable in some applications.We then present such an application in floor-planning of plane graphs. The expected grid size of the floor-plan of our linear time algorithm is improved to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$(\frac{5n}{8}+O(1))\times (\frac{23n}{24}+O(1))$\end{document}, though the worst case grid size bound of the algorithm remains \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lfloor\frac{2n+1}{3}\rfloor\times(n-1)$\end{document}, which is the same as the algorithm presented in Liao et al. (J. Algorithms 48:441–451, 2003). More... »

PAGES

726-746

References to SciGraph publications

  • 2008-01-01. On Planar Polyline Drawings in GRAPH DRAWING
  • 1988-11. A linear algorithm to find a rectangular dual of a planar triangulated graph in ALGORITHMICA
  • 1989-12. Planar graphs and poset dimension in ORDER
  • 2002-06-25. Wagner’s Theorem on Realizers in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1990-06. A theory of rectangular dual graphs in ALGORITHMICA
  • 2008-08-15. Planar Polyline Drawings via Graph Transformations in ALGORITHMICA
  • 1993-12. Floorplanning by graph dualization: L-shaped modules in ALGORITHMICA
  • 2006. Transversal Structures on Triangulations, with Application to Straight-Line Drawing in GRAPH DRAWING

    • Journal

    TITLE

    Journal of Combinatorial Optimization

    ISSUE

    4

    VOLUME

    22

    Subjects

  • FOR: Mathematical Sciences
  • FOR: Pure Mathematics
  • FOR: Applied Mathematics
  • FOR: Numerical And Computational Mathematics

    • Author Affiliations

  • Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA

    • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10878-010-9324-8

    DOI

    http://dx.doi.org/10.1007/s10878-010-9324-8

    DIMENSIONS

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

    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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA", 
          "id": "http://www.grid.ac/institutes/grid.265893.3", 
          "name": [
            "Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zhang", 
        "givenName": "Huaming", 
        "id": "sg:person.012041227127.88", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA", 
          "id": "http://www.grid.ac/institutes/grid.265893.3", 
          "name": [
            "Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sadasivam", 
        "givenName": "Sadish", 
        "id": "sg:person.015341066775.96", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015341066775.96"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf01840399", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028591325", 
          "https://doi.org/10.1007/bf01840399"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-008-9215-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032949578", 
          "https://doi.org/10.1007/s00453-008-9215-x"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00353652", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015637021", 
          "https://doi.org/10.1007/bf00353652"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11618058_17", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014203093", 
          "https://doi.org/10.1007/11618058_17"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-77537-9_22", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050806102", 
          "https://doi.org/10.1007/978-3-540-77537-9_22"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01891831", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006423518", 
          "https://doi.org/10.1007/bf01891831"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01762117", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003139574", 
          "https://doi.org/10.1007/bf01762117"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45465-9_89", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049697548", 
          "https://doi.org/10.1007/3-540-45465-9_89"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2010-04-24", 
    "datePublishedReg": "2010-04-24", 
    "description": "Let G=(V,E) and\u00a0G\u2032=(V\u2032,E\u2032) be two graphs, an adjacency-preserving transformation from\u00a0G to\u00a0G\u2032 is a one-to-many and onto mapping from V to V\u2032 satisfying the following: (1)\u00a0Each vertex v\u2208V in\u00a0G is mapped to a non-empty subset \\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}$\\mathcal{A}(v)\\subset V'$\\end{document} in\u00a0G\u2032. The subgraph induced by \\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}$\\mathcal{A}(v)$\\end{document} is a connected subgraph of\u00a0G\u2032; (2)\u00a0if u\u2260v\u2208V, then \\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}$\\mathcal{A}(u)\\cap\\mathcal{A}(v)=\\emptyset$\\end{document}; and (3)\u00a0two vertices u and v are adjacent to each other in\u00a0G if and only if subgraphs induced by \\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}$\\mathcal{A}(u)$\\end{document} and \\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}$\\mathcal{A}(v)$\\end{document} are connected in\u00a0G\u2032.In this paper, we study adjacency-preserving transformations from plane triangulations to irreducible triangulations (which are internally triangulated, with four exterior vertices and no separating triangles). As one shall see, our transformations not only preserve adjacency well, but also preserve the endowed realizers of plane triangulations well in the endowed transversal structures of the image irreducible triangulations, which may be desirable in some applications.We then present such an application in floor-planning of plane graphs. The expected grid size of the floor-plan of our linear time algorithm is improved to \\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}$(\\frac{5n}{8}+O(1))\\times (\\frac{23n}{24}+O(1))$\\end{document}, though the worst case grid size bound of the algorithm remains \\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}$\\lfloor\\frac{2n+1}{3}\\rfloor\\times(n-1)$\\end{document}, which is the same as the algorithm presented in Liao et\u00a0al. (J.\u00a0Algorithms 48:441\u2013451, 2003).", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s10878-010-9324-8", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1036683", 
        "issn": [
          "1382-6905", 
          "1573-2886"
        ], 
        "name": "Journal of Combinatorial Optimization", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "22"
      }
    ], 
    "keywords": [
      "subset", 
      "size", 
      "following", 
      "et", 
      "transformation", 
      "mapping", 
      "triangulation", 
      "applications", 
      "structure", 
      "al", 
      "non-empty subset", 
      "G\u2032", 
      "algorithm", 
      "paper", 
      "adjacency", 
      "vertices u", 
      "graph", 
      "G\u2032.", 
      "connected subgraph", 
      "grid size", 
      "plane triangulations", 
      "subgraphs", 
      "realizers", 
      "transversal structure", 
      "time algorithm", 
      "plane graph", 
      "linear time algorithm", 
      "irreducible triangulations", 
      "Liao et"
    ], 
    "name": "Improved floor-planning of graphs via adjacency-preserving transformations", 
    "pagination": "726-746", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1036096738"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10878-010-9324-8"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10878-010-9324-8", 
      "https://app.dimensions.ai/details/publication/pub.1036096738"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-05-20T07:26", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_514.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s10878-010-9324-8"
  }
]
     

    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/s10878-010-9324-8'

    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/s10878-010-9324-8'

    Turtle is a human-readable linked data format. 

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10878-010-9324-8'

    RDF/XML is a standard XML format for linked data. 

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10878-010-9324-8'


     

    This table displays all metadata directly associated to this object as RDF triples.

    134 TRIPLES      22 PREDICATES      64 URIs      46 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10878-010-9324-8 schema:about anzsrc-for:01
    2 ″ ″ anzsrc-for:0101
    3 ″ ″ anzsrc-for:0102
    4 ″ ″ anzsrc-for:0103
    5 ″ schema:author N720b38d6edc94bb1bcf86f40fb326a49
    6 ″ schema:citation sg:pub.10.1007/11618058_17
    7 ″ ″ sg:pub.10.1007/3-540-45465-9_89
    8 ″ ″ sg:pub.10.1007/978-3-540-77537-9_22
    9 ″ ″ sg:pub.10.1007/bf00353652
    10 ″ ″ sg:pub.10.1007/bf01762117
    11 ″ ″ sg:pub.10.1007/bf01840399
    12 ″ ″ sg:pub.10.1007/bf01891831
    13 ″ ″ sg:pub.10.1007/s00453-008-9215-x
    14 ″ schema:datePublished 2010-04-24
    15 ″ schema:datePublishedReg 2010-04-24
    16 ″ schema:description Let G=(V,E) and G′=(V′,E′) be two graphs, an adjacency-preserving transformation from G to G′ is a one-to-many and onto mapping from V to V′ satisfying the following: (1) Each vertex v∈V in G is mapped to a non-empty subset \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}(v)\subset V'$\end{document} in G′. The subgraph induced by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}(v)$\end{document} is a connected subgraph of G′; (2) if u≠v∈V, then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}(u)\cap\mathcal{A}(v)=\emptyset$\end{document}; and (3) two vertices u and v are adjacent to each other in G if and only if subgraphs induced by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}(u)$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}(v)$\end{document} are connected in G′.In this paper, we study adjacency-preserving transformations from plane triangulations to irreducible triangulations (which are internally triangulated, with four exterior vertices and no separating triangles). As one shall see, our transformations not only preserve adjacency well, but also preserve the endowed realizers of plane triangulations well in the endowed transversal structures of the image irreducible triangulations, which may be desirable in some applications.We then present such an application in floor-planning of plane graphs. The expected grid size of the floor-plan of our linear time algorithm is improved to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$(\frac{5n}{8}+O(1))\times (\frac{23n}{24}+O(1))$\end{document}, though the worst case grid size bound of the algorithm remains \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lfloor\frac{2n+1}{3}\rfloor\times(n-1)$\end{document}, which is the same as the algorithm presented in Liao et al. (J. Algorithms 48:441–451, 2003).
    17 ″ schema:genre article
    18 ″ schema:inLanguage en
    19 ″ schema:isAccessibleForFree false
    20 ″ schema:isPartOf Na17cfa8b94884b63ab4f61b3ee79ece2
    21 ″ ″ Ne31de457f7a2444e8dd0486579f3d5b3
    22 ″ ″ sg:journal.1036683
    23 ″ schema:keywords G′
    24 ″ ″ G′.
    25 ″ ″ Liao et
    26 ″ ″ adjacency
    27 ″ ″ al
    28 ″ ″ algorithm
    29 ″ ″ applications
    30 ″ ″ connected subgraph
    31 ″ ″ et
    32 ″ ″ following
    33 ″ ″ graph
    34 ″ ″ grid size
    35 ″ ″ irreducible triangulations
    36 ″ ″ linear time algorithm
    37 ″ ″ mapping
    38 ″ ″ non-empty subset
    39 ″ ″ paper
    40 ″ ″ plane graph
    41 ″ ″ plane triangulations
    42 ″ ″ realizers
    43 ″ ″ size
    44 ″ ″ structure
    45 ″ ″ subgraphs
    46 ″ ″ subset
    47 ″ ″ time algorithm
    48 ″ ″ transformation
    49 ″ ″ transversal structure
    50 ″ ″ triangulation
    51 ″ ″ vertices u
    52 ″ schema:name Improved floor-planning of graphs via adjacency-preserving transformations
    53 ″ schema:pagination 726-746
    54 ″ schema:productId N38cc907e22cd4479bf4a4d33702c5cc8
    55 ″ ″ Ne8d9d44edef443bd814eb2442dacec14
    56 ″ schema:sameAs https://app.dimensions.ai/details/publication/pub.1036096738
    57 ″ ″ https://doi.org/10.1007/s10878-010-9324-8
    58 ″ schema:sdDatePublished 2022-05-20T07:26
    59 ″ schema:sdLicense https://scigraph.springernature.com/explorer/license/
    60 ″ schema:sdPublisher N2d0929ce271d453f922138fe08b3160f
    61 ″ schema:url https://doi.org/10.1007/s10878-010-9324-8
    62 ″ sgo:license sg:explorer/license/
    63 ″ sgo:sdDataset articles
    64 ″ rdf:type schema:ScholarlyArticle
    65 N2d0929ce271d453f922138fe08b3160f schema:name Springer Nature - SN SciGraph project
    66 ″ rdf:type schema:Organization
    67 N38cc907e22cd4479bf4a4d33702c5cc8 schema:name dimensions_id
    68 ″ schema:value pub.1036096738
    69 ″ rdf:type schema:PropertyValue
    70 N5f7014f5a2ae4a3e80eb482b957a29ec rdf:first sg:person.015341066775.96
    71 ″ rdf:rest rdf:nil
    72 N720b38d6edc94bb1bcf86f40fb326a49 rdf:first sg:person.012041227127.88
    73 ″ rdf:rest N5f7014f5a2ae4a3e80eb482b957a29ec
    74 Na17cfa8b94884b63ab4f61b3ee79ece2 schema:issueNumber 4
    75 ″ rdf:type schema:PublicationIssue
    76 Ne31de457f7a2444e8dd0486579f3d5b3 schema:volumeNumber 22
    77 ″ rdf:type schema:PublicationVolume
    78 Ne8d9d44edef443bd814eb2442dacec14 schema:name doi
    79 ″ schema:value 10.1007/s10878-010-9324-8
    80 ″ rdf:type schema:PropertyValue
    81 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    82 ″ schema:name Mathematical Sciences
    83 ″ rdf:type schema:DefinedTerm
    84 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    85 ″ schema:name Pure Mathematics
    86 ″ rdf:type schema:DefinedTerm
    87 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    88 ″ schema:name Applied Mathematics
    89 ″ rdf:type schema:DefinedTerm
    90 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    91 ″ schema:name Numerical and Computational Mathematics
    92 ″ rdf:type schema:DefinedTerm
    93 sg:journal.1036683 schema:issn 1382-6905
    94 ″ ″ 1573-2886
    95 ″ schema:name Journal of Combinatorial Optimization
    96 ″ schema:publisher Springer Nature
    97 ″ rdf:type schema:Periodical
    98 sg:person.012041227127.88 schema:affiliation grid-institutes:grid.265893.3
    99 ″ schema:familyName Zhang
    100 ″ schema:givenName Huaming
    101 ″ schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88
    102 ″ rdf:type schema:Person
    103 sg:person.015341066775.96 schema:affiliation grid-institutes:grid.265893.3
    104 ″ schema:familyName Sadasivam
    105 ″ schema:givenName Sadish
    106 ″ schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015341066775.96
    107 ″ rdf:type schema:Person
    108 sg:pub.10.1007/11618058_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014203093
    109 ″ ″ https://doi.org/10.1007/11618058_17
    110 ″ rdf:type schema:CreativeWork
    111 sg:pub.10.1007/3-540-45465-9_89 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049697548
    112 ″ ″ https://doi.org/10.1007/3-540-45465-9_89
    113 ″ rdf:type schema:CreativeWork
    114 sg:pub.10.1007/978-3-540-77537-9_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050806102
    115 ″ ″ https://doi.org/10.1007/978-3-540-77537-9_22
    116 ″ rdf:type schema:CreativeWork
    117 sg:pub.10.1007/bf00353652 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015637021
    118 ″ ″ https://doi.org/10.1007/bf00353652
    119 ″ rdf:type schema:CreativeWork
    120 sg:pub.10.1007/bf01762117 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003139574
    121 ″ ″ https://doi.org/10.1007/bf01762117
    122 ″ rdf:type schema:CreativeWork
    123 sg:pub.10.1007/bf01840399 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028591325
    124 ″ ″ https://doi.org/10.1007/bf01840399
    125 ″ rdf:type schema:CreativeWork
    126 sg:pub.10.1007/bf01891831 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006423518
    127 ″ ″ https://doi.org/10.1007/bf01891831
    128 ″ rdf:type schema:CreativeWork
    129 sg:pub.10.1007/s00453-008-9215-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1032949578
    130 ″ ″ https://doi.org/10.1007/s00453-008-9215-x
    131 ″ rdf:type schema:CreativeWork
    132 grid-institutes:grid.265893.3 schema:alternateName Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA
    133 ″ schema:name Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA
    134 ″ rdf:type schema:Organization
     




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

    ...