On the Validity of Hierarchical Decompositions View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2001-07-31

AUTHORS

Irene Finocchi , Rossella Petreschi

ABSTRACT

Hierarchical decompositions are a useful tool for drawing large graphs. Such decompositions can be represented by means of a data structure called hierarchy tree. In this paper we introduce the notion of P-validity of hierarchy trees with respect to a given property P: this notion reflects the similarity between the topological structure of the original graph and of any high-level representation of it obtained from the hierarchy tree. We study the P-validity when the clustered graph is a tree and property P is the acyclicity, presenting a structure theorem for the P-validity of hierarchy trees under these hypotheses. More... »

PAGES

368-374

References to SciGraph publications

  • 1997. Multilevel visualization of clustered graphs in GRAPH DRAWING
  • 1995. Planarity for clustered graphs in ALGORITHMS — ESA '95
  • 2001. Hierarchical Clustering of Trees: Algorithms and Experiments in ALGORITHM ENGINEERING AND EXPERIMENTATION
  • Book

    TITLE

    Computing and Combinatorics

    ISBN

    978-3-540-42494-9
    978-3-540-44679-8

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-44679-6_40

    DOI

    http://dx.doi.org/10.1007/3-540-44679-6_40

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "name": [
                "Department of Computer Science, University of Rome, \u201cLa Sapienza\u201d"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Finocchi", 
            "givenName": "Irene", 
            "id": "sg:person.014240412541.72", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014240412541.72"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "Department of Computer Science, University of Rome, \u201cLa Sapienza\u201d"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Petreschi", 
            "givenName": "Rossella", 
            "id": "sg:person.011402427702.78", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-44808-x_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022717534", 
              "https://doi.org/10.1007/3-540-44808-x_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-60313-1_145", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027740289", 
              "https://doi.org/10.1007/3-540-60313-1_145"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-62495-3_41", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029153456", 
              "https://doi.org/10.1007/3-540-62495-3_41"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.7155/jgaa.00024", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1073626310"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2001-07-31", 
        "datePublishedReg": "2001-07-31", 
        "description": "Hierarchical decompositions are a useful tool for drawing large graphs. Such decompositions can be represented by means of a data structure called hierarchy tree. In this paper we introduce the notion of P-validity of hierarchy trees with respect to a given property P: this notion reflects the similarity between the topological structure of the original graph and of any high-level representation of it obtained from the hierarchy tree. We study the P-validity when the clustered graph is a tree and property P is the acyclicity, presenting a structure theorem for the P-validity of hierarchy trees under these hypotheses.", 
        "editor": [
          {
            "familyName": "Wang", 
            "givenName": "Jie", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-44679-6_40", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-42494-9", 
            "978-3-540-44679-8"
          ], 
          "name": "Computing and Combinatorics", 
          "type": "Book"
        }, 
        "name": "On the Validity of Hierarchical Decompositions", 
        "pagination": "368-374", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-44679-6_40"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "40b19f7401ef203fab83b4c84eb7d87d7e61a04fe8854cb764640b4e78619059"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1013580317"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-44679-6_40", 
          "https://app.dimensions.ai/details/publication/pub.1013580317"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T05:36", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000346_0000000346/records_99833_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F3-540-44679-6_40"
      }
    ]
     

    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-44679-6_40'

    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-44679-6_40'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44679-6_40'

    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-44679-6_40'


     

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

    88 TRIPLES      23 PREDICATES      30 URIs      19 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-44679-6_40 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Ne658a601b62d42a7b3629c98970bed8a
    4 schema:citation sg:pub.10.1007/3-540-44808-x_9
    5 sg:pub.10.1007/3-540-60313-1_145
    6 sg:pub.10.1007/3-540-62495-3_41
    7 https://doi.org/10.7155/jgaa.00024
    8 schema:datePublished 2001-07-31
    9 schema:datePublishedReg 2001-07-31
    10 schema:description Hierarchical decompositions are a useful tool for drawing large graphs. Such decompositions can be represented by means of a data structure called hierarchy tree. In this paper we introduce the notion of P-validity of hierarchy trees with respect to a given property P: this notion reflects the similarity between the topological structure of the original graph and of any high-level representation of it obtained from the hierarchy tree. We study the P-validity when the clustered graph is a tree and property P is the acyclicity, presenting a structure theorem for the P-validity of hierarchy trees under these hypotheses.
    11 schema:editor N5edc99f79981447fb388ba213fdaab8b
    12 schema:genre chapter
    13 schema:inLanguage en
    14 schema:isAccessibleForFree true
    15 schema:isPartOf N7844fce12cad4b32b3ff7a6b2f23a052
    16 schema:name On the Validity of Hierarchical Decompositions
    17 schema:pagination 368-374
    18 schema:productId N06c203e6dcce499d8f81ea9cae6ed662
    19 N0a398ca232e84e4d8ace8552f17dc4d9
    20 Nedb063774b2740e49ebbf317c859ed0f
    21 schema:publisher N8cb5ed5f15b740b587890d19fcdd90fa
    22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013580317
    23 https://doi.org/10.1007/3-540-44679-6_40
    24 schema:sdDatePublished 2019-04-16T05:36
    25 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    26 schema:sdPublisher Ne348115e70db4ae0814a4a1ac650c436
    27 schema:url https://link.springer.com/10.1007%2F3-540-44679-6_40
    28 sgo:license sg:explorer/license/
    29 sgo:sdDataset chapters
    30 rdf:type schema:Chapter
    31 N06c203e6dcce499d8f81ea9cae6ed662 schema:name dimensions_id
    32 schema:value pub.1013580317
    33 rdf:type schema:PropertyValue
    34 N0a398ca232e84e4d8ace8552f17dc4d9 schema:name readcube_id
    35 schema:value 40b19f7401ef203fab83b4c84eb7d87d7e61a04fe8854cb764640b4e78619059
    36 rdf:type schema:PropertyValue
    37 N5edc99f79981447fb388ba213fdaab8b rdf:first Ndbf1692107b448cf875323a134511762
    38 rdf:rest rdf:nil
    39 N604550f7edf547fda4ba52a8630f74c8 rdf:first sg:person.011402427702.78
    40 rdf:rest rdf:nil
    41 N7844fce12cad4b32b3ff7a6b2f23a052 schema:isbn 978-3-540-42494-9
    42 978-3-540-44679-8
    43 schema:name Computing and Combinatorics
    44 rdf:type schema:Book
    45 N8cb5ed5f15b740b587890d19fcdd90fa schema:location Berlin, Heidelberg
    46 schema:name Springer Berlin Heidelberg
    47 rdf:type schema:Organisation
    48 Ndbf1692107b448cf875323a134511762 schema:familyName Wang
    49 schema:givenName Jie
    50 rdf:type schema:Person
    51 Ne348115e70db4ae0814a4a1ac650c436 schema:name Springer Nature - SN SciGraph project
    52 rdf:type schema:Organization
    53 Ne658a601b62d42a7b3629c98970bed8a rdf:first sg:person.014240412541.72
    54 rdf:rest N604550f7edf547fda4ba52a8630f74c8
    55 Nedb063774b2740e49ebbf317c859ed0f schema:name doi
    56 schema:value 10.1007/3-540-44679-6_40
    57 rdf:type schema:PropertyValue
    58 Nef6e122ae9894acc9b4ba541707c5d06 schema:name Department of Computer Science, University of Rome, “La Sapienza”
    59 rdf:type schema:Organization
    60 Nfcdad05aae904a858b623b6d08ce1d79 schema:name Department of Computer Science, University of Rome, “La Sapienza”
    61 rdf:type schema:Organization
    62 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    63 schema:name Information and Computing Sciences
    64 rdf:type schema:DefinedTerm
    65 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    66 schema:name Computation Theory and Mathematics
    67 rdf:type schema:DefinedTerm
    68 sg:person.011402427702.78 schema:affiliation Nfcdad05aae904a858b623b6d08ce1d79
    69 schema:familyName Petreschi
    70 schema:givenName Rossella
    71 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
    72 rdf:type schema:Person
    73 sg:person.014240412541.72 schema:affiliation Nef6e122ae9894acc9b4ba541707c5d06
    74 schema:familyName Finocchi
    75 schema:givenName Irene
    76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014240412541.72
    77 rdf:type schema:Person
    78 sg:pub.10.1007/3-540-44808-x_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022717534
    79 https://doi.org/10.1007/3-540-44808-x_9
    80 rdf:type schema:CreativeWork
    81 sg:pub.10.1007/3-540-60313-1_145 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027740289
    82 https://doi.org/10.1007/3-540-60313-1_145
    83 rdf:type schema:CreativeWork
    84 sg:pub.10.1007/3-540-62495-3_41 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029153456
    85 https://doi.org/10.1007/3-540-62495-3_41
    86 rdf:type schema:CreativeWork
    87 https://doi.org/10.7155/jgaa.00024 schema:sameAs https://app.dimensions.ai/details/publication/pub.1073626310
    88 rdf:type schema:CreativeWork
     




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


    ...