An efficient orthogonal grid drawing algorithm for cubic graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2005-06-20

AUTHORS

Tiziana Calamoneri , Rossella Petreschi

ABSTRACT

In this paper we present a new algorithm that constructs an orthogonal drawing of a graph G with degree at most three. Even if we do not require any limitations neither to planar nor to biconnected graphs, we reach the best known results in the literarture: each edge has at most 1 bend, the total number of bends is ≤ n/2+1, and the area is ≤(n/2−1)2. More... »

PAGES

31-40

References to SciGraph publications

Book

TITLE

Computing and Combinatorics

ISBN

978-3-540-60216-3
978-3-540-44733-7

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bfb0030817

DOI

http://dx.doi.org/10.1007/bfb0030817

DIMENSIONS

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


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/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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dept. of Computer Science, University of Rome \u201cLa Sapienza\u201d, Via Salaria 113, 00198, Roma, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Calamoneri", 
        "givenName": "Tiziana", 
        "id": "sg:person.013577775161.22", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013577775161.22"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dept. of Computer Science, University of Rome \u201cLa Sapienza\u201d, 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"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/3-540-57155-8_244", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005416239", 
          "https://doi.org/10.1007/3-540-57155-8_244"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/358645.358660", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010223097"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0049394", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015756399", 
          "https://doi.org/10.1007/bfb0049394"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-58950-3_355", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020372913", 
          "https://doi.org/10.1007/3-540-58950-3_355"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02086606", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024228802", 
          "https://doi.org/10.1007/bf02086606"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02086606", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024228802", 
          "https://doi.org/10.1007/bf02086606"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2005-06-20", 
    "datePublishedReg": "2005-06-20", 
    "description": "In this paper we present a new algorithm that constructs an orthogonal drawing of a graph G with degree at most three. Even if we do not require any limitations neither to planar nor to biconnected graphs, we reach the best known results in the literarture: each edge has at most 1 bend, the total number of bends is \u2264 n/2+1, and the area is \u2264(n/2\u22121)2.", 
    "editor": [
      {
        "familyName": "Du", 
        "givenName": "Ding-Zhu", 
        "type": "Person"
      }, 
      {
        "familyName": "Li", 
        "givenName": "Ming", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/bfb0030817", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-60216-3", 
        "978-3-540-44733-7"
      ], 
      "name": "Computing and Combinatorics", 
      "type": "Book"
    }, 
    "name": "An efficient orthogonal grid drawing algorithm for cubic graphs", 
    "pagination": "31-40", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1030999160"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bfb0030817"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "93ae0248d97fbc60a2e139953a55c9b26ee57279c75378dae43b2422d68bb32b"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/bfb0030817", 
      "https://app.dimensions.ai/details/publication/pub.1030999160"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T09:43", 
    "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/0000000374_0000000374/records_119754_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2FBFb0030817"
  }
]
 

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/bfb0030817'

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/bfb0030817'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bfb0030817'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bfb0030817'


 

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

96 TRIPLES      23 PREDICATES      31 URIs      19 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bfb0030817 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N03083ec5743542fe893cb0648c220fd2
4 schema:citation sg:pub.10.1007/3-540-57155-8_244
5 sg:pub.10.1007/3-540-58950-3_355
6 sg:pub.10.1007/bf02086606
7 sg:pub.10.1007/bfb0049394
8 https://doi.org/10.1145/358645.358660
9 schema:datePublished 2005-06-20
10 schema:datePublishedReg 2005-06-20
11 schema:description In this paper we present a new algorithm that constructs an orthogonal drawing of a graph G with degree at most three. Even if we do not require any limitations neither to planar nor to biconnected graphs, we reach the best known results in the literarture: each edge has at most 1 bend, the total number of bends is ≤ n/2+1, and the area is ≤(n/2−1)2.
12 schema:editor N5b7d3f5e51104de38b0e20011b3682f8
13 schema:genre chapter
14 schema:inLanguage en
15 schema:isAccessibleForFree false
16 schema:isPartOf N930d4f59a11e4232b27123f55951bc69
17 schema:name An efficient orthogonal grid drawing algorithm for cubic graphs
18 schema:pagination 31-40
19 schema:productId N4d625d7285344cada89d8ab95b3815f7
20 N558aff9116ca4b1aa8abe9f39044c84e
21 N5a0c212864d6483397210b1992ce0459
22 schema:publisher Ne3018a34346443b4ac24ef028a57c47e
23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030999160
24 https://doi.org/10.1007/bfb0030817
25 schema:sdDatePublished 2019-04-16T09:43
26 schema:sdLicense https://scigraph.springernature.com/explorer/license/
27 schema:sdPublisher N3ac11629b23546d38bed325389bc230a
28 schema:url https://link.springer.com/10.1007%2FBFb0030817
29 sgo:license sg:explorer/license/
30 sgo:sdDataset chapters
31 rdf:type schema:Chapter
32 N03083ec5743542fe893cb0648c220fd2 rdf:first sg:person.013577775161.22
33 rdf:rest N5b36015a5245482796a1286fc79864d6
34 N143a80bd4bd14590bc8563e2f86e71d8 rdf:first Nb789364667d84f438aefa7ecb5cdfd49
35 rdf:rest rdf:nil
36 N3ac11629b23546d38bed325389bc230a schema:name Springer Nature - SN SciGraph project
37 rdf:type schema:Organization
38 N4510c4690c6f4b149635f16d6c389a33 schema:familyName Du
39 schema:givenName Ding-Zhu
40 rdf:type schema:Person
41 N4d625d7285344cada89d8ab95b3815f7 schema:name dimensions_id
42 schema:value pub.1030999160
43 rdf:type schema:PropertyValue
44 N558aff9116ca4b1aa8abe9f39044c84e schema:name readcube_id
45 schema:value 93ae0248d97fbc60a2e139953a55c9b26ee57279c75378dae43b2422d68bb32b
46 rdf:type schema:PropertyValue
47 N5a0c212864d6483397210b1992ce0459 schema:name doi
48 schema:value 10.1007/bfb0030817
49 rdf:type schema:PropertyValue
50 N5b36015a5245482796a1286fc79864d6 rdf:first sg:person.011402427702.78
51 rdf:rest rdf:nil
52 N5b7d3f5e51104de38b0e20011b3682f8 rdf:first N4510c4690c6f4b149635f16d6c389a33
53 rdf:rest N143a80bd4bd14590bc8563e2f86e71d8
54 N930d4f59a11e4232b27123f55951bc69 schema:isbn 978-3-540-44733-7
55 978-3-540-60216-3
56 schema:name Computing and Combinatorics
57 rdf:type schema:Book
58 Nb789364667d84f438aefa7ecb5cdfd49 schema:familyName Li
59 schema:givenName Ming
60 rdf:type schema:Person
61 Ne3018a34346443b4ac24ef028a57c47e schema:location Berlin, Heidelberg
62 schema:name Springer Berlin Heidelberg
63 rdf:type schema:Organisation
64 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
65 schema:name Mathematical Sciences
66 rdf:type schema:DefinedTerm
67 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
68 schema:name Pure Mathematics
69 rdf:type schema:DefinedTerm
70 sg:person.011402427702.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
71 schema:familyName Petreschi
72 schema:givenName Rossella
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
74 rdf:type schema:Person
75 sg:person.013577775161.22 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
76 schema:familyName Calamoneri
77 schema:givenName Tiziana
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013577775161.22
79 rdf:type schema:Person
80 sg:pub.10.1007/3-540-57155-8_244 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005416239
81 https://doi.org/10.1007/3-540-57155-8_244
82 rdf:type schema:CreativeWork
83 sg:pub.10.1007/3-540-58950-3_355 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020372913
84 https://doi.org/10.1007/3-540-58950-3_355
85 rdf:type schema:CreativeWork
86 sg:pub.10.1007/bf02086606 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024228802
87 https://doi.org/10.1007/bf02086606
88 rdf:type schema:CreativeWork
89 sg:pub.10.1007/bfb0049394 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015756399
90 https://doi.org/10.1007/bfb0049394
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1145/358645.358660 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010223097
93 rdf:type schema:CreativeWork
94 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
95 schema:name Dept. of Computer Science, University of Rome “La Sapienza”, Via Salaria 113, 00198, Roma, Italy
96 rdf:type schema:Organization
 




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


...