Structure-Preserving Hierarchical Decompositions View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2005-11

AUTHORS

Irene Finocchi, Rossella Petreschi

ABSTRACT

A hierarchy tree of a graph G is a rooted tree whose leaves are the vertices of G; the internal nodes are usually called clusters. Hierarchy trees are well suited for representing hierarchical decompositions of graphs. In this paper we introduce the notion of P-validity of hierarchy trees with respect to a given graph property P. This notion reflects the similarity between any high-level representation of G obtained from the hierarchy tree and the topological structure of G. Maintaining the properties of a graph at any level of abstraction is especially relevant in graph drawing applications. We present a structural characterization of P-valid hierarchy trees when the clustered graph is a tree and property P is the acyclicity. Besides being interesting in its own right, our structure theorem can be used in the design of a polynomial time algorithm for recognizing P-valid hierarchy trees. More... »

PAGES

687-700

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00224-004-1132-z

DOI

http://dx.doi.org/10.1007/s00224-004-1132-z

DIMENSIONS

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


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": {
          "alternateName": "University of Rome Tor Vergata", 
          "id": "https://www.grid.ac/institutes/grid.6530.0", 
          "name": [
            "Dipartimento di Informatica, Sistemi e Produzione, Universita degli Studi di Roma \"Tor Vergata\",  Via del Politecnico 1, 00133 Roma, Italy"
          ], 
          "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": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dipartimento di Informatica,  Universita degli Studi di Roma \"La Sapienza\", Via Salaria 113, 00198 Roma, Italy"
          ], 
          "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"
      }
    ], 
    "datePublished": "2005-11", 
    "datePublishedReg": "2005-11-01", 
    "description": "A hierarchy tree of a graph G is a rooted tree whose leaves are the vertices of G; the internal nodes are usually called clusters. Hierarchy trees are well suited for representing hierarchical decompositions of graphs. In this paper we introduce the notion of P-validity of hierarchy trees with respect to a given graph property P. This notion reflects the similarity between any high-level representation of G obtained from the hierarchy tree and the topological structure of G. Maintaining the properties of a graph at any level of abstraction is especially relevant in graph drawing applications. We present a structural characterization of P-valid hierarchy trees when the clustered graph is a tree and property P is the acyclicity. Besides being interesting in its own right, our structure theorem can be used in the design of a polynomial time algorithm for recognizing P-valid hierarchy trees.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00224-004-1132-z", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1052098", 
        "issn": [
          "1432-4350", 
          "1433-0490"
        ], 
        "name": "Theory of Computing Systems", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "6", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "38"
      }
    ], 
    "name": "Structure-Preserving Hierarchical Decompositions", 
    "pagination": "687-700", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "10fcea8baaf83acef3bd4f555f22e382f6102d1a8b3ee1ad828b186490e819ba"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00224-004-1132-z"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1003565965"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00224-004-1132-z", 
      "https://app.dimensions.ai/details/publication/pub.1003565965"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T14:00", 
    "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/0000000001_0000000264/records_8660_00000479.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/s00224-004-1132-z"
  }
]
 

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/s00224-004-1132-z'

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/s00224-004-1132-z'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-004-1132-z'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-004-1132-z'


 

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

71 TRIPLES      20 PREDICATES      27 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00224-004-1132-z schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Ne8610127da894c629770f721c3fe4ef1
4 schema:datePublished 2005-11
5 schema:datePublishedReg 2005-11-01
6 schema:description A hierarchy tree of a graph G is a rooted tree whose leaves are the vertices of G; the internal nodes are usually called clusters. Hierarchy trees are well suited for representing hierarchical decompositions of graphs. In this paper we introduce the notion of P-validity of hierarchy trees with respect to a given graph property P. This notion reflects the similarity between any high-level representation of G obtained from the hierarchy tree and the topological structure of G. Maintaining the properties of a graph at any level of abstraction is especially relevant in graph drawing applications. We present a structural characterization of P-valid hierarchy trees when the clustered graph is a tree and property P is the acyclicity. Besides being interesting in its own right, our structure theorem can be used in the design of a polynomial time algorithm for recognizing P-valid hierarchy trees.
7 schema:genre research_article
8 schema:inLanguage en
9 schema:isAccessibleForFree false
10 schema:isPartOf N071ee8641a7e490881a2fd416d54b912
11 N46a30ed6d0964b61974959e65d6d810c
12 sg:journal.1052098
13 schema:name Structure-Preserving Hierarchical Decompositions
14 schema:pagination 687-700
15 schema:productId N2da1dcf9e1154570bfbfa9020af3324f
16 Nb17639cd281e4aea8ea308a8cf9b9782
17 Nc85ad9534d9246009ae48aa7f2caca9e
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003565965
19 https://doi.org/10.1007/s00224-004-1132-z
20 schema:sdDatePublished 2019-04-10T14:00
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher N77ccaaf5974b4fa68cfbf219684dc7ca
23 schema:url http://link.springer.com/10.1007/s00224-004-1132-z
24 sgo:license sg:explorer/license/
25 sgo:sdDataset articles
26 rdf:type schema:ScholarlyArticle
27 N071ee8641a7e490881a2fd416d54b912 schema:issueNumber 6
28 rdf:type schema:PublicationIssue
29 N2da1dcf9e1154570bfbfa9020af3324f schema:name readcube_id
30 schema:value 10fcea8baaf83acef3bd4f555f22e382f6102d1a8b3ee1ad828b186490e819ba
31 rdf:type schema:PropertyValue
32 N39e1943b9f8a4830a3203f7b778237b0 rdf:first sg:person.011402427702.78
33 rdf:rest rdf:nil
34 N46a30ed6d0964b61974959e65d6d810c schema:volumeNumber 38
35 rdf:type schema:PublicationVolume
36 N77ccaaf5974b4fa68cfbf219684dc7ca schema:name Springer Nature - SN SciGraph project
37 rdf:type schema:Organization
38 Nb17639cd281e4aea8ea308a8cf9b9782 schema:name doi
39 schema:value 10.1007/s00224-004-1132-z
40 rdf:type schema:PropertyValue
41 Nc85ad9534d9246009ae48aa7f2caca9e schema:name dimensions_id
42 schema:value pub.1003565965
43 rdf:type schema:PropertyValue
44 Ne8610127da894c629770f721c3fe4ef1 rdf:first sg:person.014240412541.72
45 rdf:rest N39e1943b9f8a4830a3203f7b778237b0
46 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
47 schema:name Information and Computing Sciences
48 rdf:type schema:DefinedTerm
49 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
50 schema:name Computation Theory and Mathematics
51 rdf:type schema:DefinedTerm
52 sg:journal.1052098 schema:issn 1432-4350
53 1433-0490
54 schema:name Theory of Computing Systems
55 rdf:type schema:Periodical
56 sg:person.011402427702.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
57 schema:familyName Petreschi
58 schema:givenName Rossella
59 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
60 rdf:type schema:Person
61 sg:person.014240412541.72 schema:affiliation https://www.grid.ac/institutes/grid.6530.0
62 schema:familyName Finocchi
63 schema:givenName Irene
64 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014240412541.72
65 rdf:type schema:Person
66 https://www.grid.ac/institutes/grid.6530.0 schema:alternateName University of Rome Tor Vergata
67 schema:name Dipartimento di Informatica, Sistemi e Produzione, Universita degli Studi di Roma "Tor Vergata", Via del Politecnico 1, 00133 Roma, Italy
68 rdf:type schema:Organization
69 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
70 schema:name Dipartimento di Informatica, Universita degli Studi di Roma "La Sapienza", Via Salaria 113, 00198 Roma, Italy
71 rdf:type schema:Organization
 




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


...