On the Tree-Degree of Graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2001-10-02

AUTHORS

Maw-Shang Chang , Haiko Müller

ABSTRACT

Every graph is the edge intersection graph of subtrees of a tree. The tree-degree of a graph is the minimum maximal degree of the underlying tree for which there exists a subtree intersection model. Computing the tree-degree is NP-complete even for planar graphs, but polynomial time algorithms exist for outer-planar graphs, diamond-free graphs and chordal graphs. The number of minimal separators of graphs with bounded tree-degree is polynomial. This implies that the treewidth of graphs with bounded tree-degree can be computed efficiently, even without the model given in advance. More... »

PAGES

44-54

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-45477-2_6

DOI

http://dx.doi.org/10.1007/3-540-45477-2_6

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, Chung Cheng University, Ming-Shiun, Chiayi 621, Taiwan", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Department of Computer Science and Information Engineering, Chung Cheng University, Ming-Shiun, Chiayi 621, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chang", 
        "givenName": "Maw-Shang", 
        "id": "sg:person.013174232477.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "School of Computing, University of Leeds, LS2 9JT, Leeds, UK", 
          "id": "http://www.grid.ac/institutes/grid.9909.9", 
          "name": [
            "School of Computing, University of Leeds, LS2 9JT, Leeds, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "M\u00fcller", 
        "givenName": "Haiko", 
        "id": "sg:person.012247602107.88", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012247602107.88"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2001-10-02", 
    "datePublishedReg": "2001-10-02", 
    "description": "Every graph is the edge intersection graph of subtrees of a tree. The tree-degree of a graph is the minimum maximal degree of the underlying tree for which there exists a subtree intersection model. Computing the tree-degree is NP-complete even for planar graphs, but polynomial time algorithms exist for outer-planar graphs, diamond-free graphs and chordal graphs. The number of minimal separators of graphs with bounded tree-degree is polynomial. This implies that the treewidth of graphs with bounded tree-degree can be computed efficiently, even without the model given in advance.", 
    "editor": [
      {
        "familyName": "Brandst\u00e4dt", 
        "givenName": "Andreas", 
        "type": "Person"
      }, 
      {
        "familyName": "Le", 
        "givenName": "Van Bang", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-45477-2_6", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-42707-0", 
        "978-3-540-45477-9"
      ], 
      "name": "Graph-Theoretic Concepts in Computer Science", 
      "type": "Book"
    }, 
    "keywords": [
      "treewidth of graphs", 
      "polynomial time algorithm", 
      "time algorithm", 
      "outer-planar graphs", 
      "minimal separators", 
      "graph", 
      "diamond-free graphs", 
      "chordal graphs", 
      "intersection model", 
      "intersection graph", 
      "planar graphs", 
      "algorithm", 
      "treewidth", 
      "edge intersection graphs", 
      "subtrees", 
      "trees", 
      "NP", 
      "underlying tree", 
      "maximal degree", 
      "model", 
      "advances", 
      "number", 
      "degree", 
      "separator", 
      "minimum maximal degree", 
      "subtree intersection model", 
      "Tree-Degree"
    ], 
    "name": "On the Tree-Degree of Graphs", 
    "pagination": "44-54", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1007807444"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-45477-2_6"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-45477-2_6", 
      "https://app.dimensions.ai/details/publication/pub.1007807444"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:59", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_39.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-45477-2_6"
  }
]
 

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-45477-2_6'

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-45477-2_6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-45477-2_6'

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-45477-2_6'


 

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

102 TRIPLES      23 PREDICATES      52 URIs      45 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-45477-2_6 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Ne58e16445e814cea8846c90705a95d63
4 schema:datePublished 2001-10-02
5 schema:datePublishedReg 2001-10-02
6 schema:description Every graph is the edge intersection graph of subtrees of a tree. The tree-degree of a graph is the minimum maximal degree of the underlying tree for which there exists a subtree intersection model. Computing the tree-degree is NP-complete even for planar graphs, but polynomial time algorithms exist for outer-planar graphs, diamond-free graphs and chordal graphs. The number of minimal separators of graphs with bounded tree-degree is polynomial. This implies that the treewidth of graphs with bounded tree-degree can be computed efficiently, even without the model given in advance.
7 schema:editor Ne435566fb4a5415686c5450df615b635
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N1a23286dbac048599d6a8c72b8ec58cd
12 schema:keywords NP
13 Tree-Degree
14 advances
15 algorithm
16 chordal graphs
17 degree
18 diamond-free graphs
19 edge intersection graphs
20 graph
21 intersection graph
22 intersection model
23 maximal degree
24 minimal separators
25 minimum maximal degree
26 model
27 number
28 outer-planar graphs
29 planar graphs
30 polynomial time algorithm
31 separator
32 subtree intersection model
33 subtrees
34 time algorithm
35 trees
36 treewidth
37 treewidth of graphs
38 underlying tree
39 schema:name On the Tree-Degree of Graphs
40 schema:pagination 44-54
41 schema:productId N1214833aca7748d5842721f7a171c3c6
42 N5bd0a77ced0741f2848fc015d0c176ad
43 schema:publisher Nbd8dc9e4ce774dcd943197fa400ab8e8
44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007807444
45 https://doi.org/10.1007/3-540-45477-2_6
46 schema:sdDatePublished 2021-11-01T18:59
47 schema:sdLicense https://scigraph.springernature.com/explorer/license/
48 schema:sdPublisher N7b00a6476d614e418c039e562e3cf36b
49 schema:url https://doi.org/10.1007/3-540-45477-2_6
50 sgo:license sg:explorer/license/
51 sgo:sdDataset chapters
52 rdf:type schema:Chapter
53 N1214833aca7748d5842721f7a171c3c6 schema:name doi
54 schema:value 10.1007/3-540-45477-2_6
55 rdf:type schema:PropertyValue
56 N1a23286dbac048599d6a8c72b8ec58cd schema:isbn 978-3-540-42707-0
57 978-3-540-45477-9
58 schema:name Graph-Theoretic Concepts in Computer Science
59 rdf:type schema:Book
60 N20ff9c57f4ae40dab899314310be088f rdf:first sg:person.012247602107.88
61 rdf:rest rdf:nil
62 N5bd0a77ced0741f2848fc015d0c176ad schema:name dimensions_id
63 schema:value pub.1007807444
64 rdf:type schema:PropertyValue
65 N7b00a6476d614e418c039e562e3cf36b schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 Nba3062070d1348a8966bd806c0bf0d67 schema:familyName Le
68 schema:givenName Van Bang
69 rdf:type schema:Person
70 Nbd8dc9e4ce774dcd943197fa400ab8e8 schema:name Springer Nature
71 rdf:type schema:Organisation
72 Nc1b36427fc2945af9eea7094de2230d1 schema:familyName Brandstädt
73 schema:givenName Andreas
74 rdf:type schema:Person
75 Ne435566fb4a5415686c5450df615b635 rdf:first Nc1b36427fc2945af9eea7094de2230d1
76 rdf:rest Nfd7edf2097e341b4a9334ce190cc6e2a
77 Ne58e16445e814cea8846c90705a95d63 rdf:first sg:person.013174232477.45
78 rdf:rest N20ff9c57f4ae40dab899314310be088f
79 Nfd7edf2097e341b4a9334ce190cc6e2a rdf:first Nba3062070d1348a8966bd806c0bf0d67
80 rdf:rest rdf:nil
81 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
82 schema:name Information and Computing Sciences
83 rdf:type schema:DefinedTerm
84 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
85 schema:name Computation Theory and Mathematics
86 rdf:type schema:DefinedTerm
87 sg:person.012247602107.88 schema:affiliation grid-institutes:grid.9909.9
88 schema:familyName Müller
89 schema:givenName Haiko
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012247602107.88
91 rdf:type schema:Person
92 sg:person.013174232477.45 schema:affiliation grid-institutes:None
93 schema:familyName Chang
94 schema:givenName Maw-Shang
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45
96 rdf:type schema:Person
97 grid-institutes:None schema:alternateName Department of Computer Science and Information Engineering, Chung Cheng University, Ming-Shiun, Chiayi 621, Taiwan
98 schema:name Department of Computer Science and Information Engineering, Chung Cheng University, Ming-Shiun, Chiayi 621, Taiwan
99 rdf:type schema:Organization
100 grid-institutes:grid.9909.9 schema:alternateName School of Computing, University of Leeds, LS2 9JT, Leeds, UK
101 schema:name School of Computing, University of Leeds, LS2 9JT, Leeds, UK
102 rdf:type schema:Organization
 




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


...