Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs (extended abstract) View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1993

AUTHORS

Giuseppe Di Battista , Giuseppe Liotta , Francesco Vargiu

ABSTRACT

An orthogonal drawing of a graph is a planar drawing such that all the edges are polygonal chains of horizontal and vertical segments. Finding the planar embedding of a planar graph such that its orthogonal drawing has the minimum number of bends is a fundamental open problem in graph drawing. This paper provides the first partial solution to the problem. It gives a new combinatorial characterization of orthogonal drawings based on the concept of spirality and provides a polynomial-time algorithm for series-parallel graphs and biconnected 3-planar graphs. More... »

PAGES

151-162

Book

TITLE

Algorithms and Data Structures

ISBN

978-3-540-57155-1
978-3-540-47918-5

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-57155-8_244

DOI

http://dx.doi.org/10.1007/3-540-57155-8_244

DIMENSIONS

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


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": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dipartimento di Informatica e Sistemistica, Universit\u00e0 di Roma \u201cLa Sapienza\u201d, via Salaria 113, I-00198\u00a0Roma, Italia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Di Battista", 
        "givenName": "Giuseppe", 
        "id": "sg:person.0616310175.56", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0616310175.56"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dipartimento di Informatica e Sistemistica, Universit\u00e0 di Roma \u201cLa Sapienza\u201d, via Salaria 113, I-00198\u00a0Roma, Italia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Liotta", 
        "givenName": "Giuseppe", 
        "id": "sg:person.0616776646.71", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0616776646.71"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dipartimento di Informatica e Sistemistica, Universit\u00e0 di Roma \u201cLa Sapienza\u201d, via Salaria 113, I-00198\u00a0Roma, Italia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vargiu", 
        "givenName": "Francesco", 
        "id": "sg:person.012154640211.03", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012154640211.03"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0304-3975(88)90123-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030081374"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/31.34669", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061153032"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0216030", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841976"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1993", 
    "datePublishedReg": "1993-01-01", 
    "description": "An orthogonal drawing of a graph is a planar drawing such that all the edges are polygonal chains of horizontal and vertical segments. Finding the planar embedding of a planar graph such that its orthogonal drawing has the minimum number of bends is a fundamental open problem in graph drawing. This paper provides the first partial solution to the problem. It gives a new combinatorial characterization of orthogonal drawings based on the concept of spirality and provides a polynomial-time algorithm for series-parallel graphs and biconnected 3-planar graphs.", 
    "editor": [
      {
        "familyName": "Dehne", 
        "givenName": "Frank", 
        "type": "Person"
      }, 
      {
        "familyName": "Sack", 
        "givenName": "J\u00f6rg-R\u00fcdiger", 
        "type": "Person"
      }, 
      {
        "familyName": "Santoro", 
        "givenName": "Nicola", 
        "type": "Person"
      }, 
      {
        "familyName": "Whitesides", 
        "givenName": "Sue", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-57155-8_244", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-57155-1", 
        "978-3-540-47918-5"
      ], 
      "name": "Algorithms and Data Structures", 
      "type": "Book"
    }, 
    "name": "Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs (extended abstract)", 
    "pagination": "151-162", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-57155-8_244"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "19ce4d486f1188f2de261467a9e1584eaff1dbb661d1d41fcf8a31ef4b1ca259"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1005416239"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-57155-8_244", 
      "https://app.dimensions.ai/details/publication/pub.1005416239"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T22:53", 
    "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_8695_00000246.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-57155-8_244"
  }
]
 

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-57155-8_244'

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-57155-8_244'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-57155-8_244'

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-57155-8_244'


 

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

103 TRIPLES      23 PREDICATES      30 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-57155-8_244 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N5e49526f0291445498f3b74f3e273c0c
4 schema:citation https://doi.org/10.1016/0304-3975(88)90123-5
5 https://doi.org/10.1109/31.34669
6 https://doi.org/10.1137/0216030
7 schema:datePublished 1993
8 schema:datePublishedReg 1993-01-01
9 schema:description An orthogonal drawing of a graph is a planar drawing such that all the edges are polygonal chains of horizontal and vertical segments. Finding the planar embedding of a planar graph such that its orthogonal drawing has the minimum number of bends is a fundamental open problem in graph drawing. This paper provides the first partial solution to the problem. It gives a new combinatorial characterization of orthogonal drawings based on the concept of spirality and provides a polynomial-time algorithm for series-parallel graphs and biconnected 3-planar graphs.
10 schema:editor N0db0531719fe421ea3e6a8120b1f789a
11 schema:genre chapter
12 schema:inLanguage en
13 schema:isAccessibleForFree false
14 schema:isPartOf N943f9b92eb4b4e55b41c1281f0925d7f
15 schema:name Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs (extended abstract)
16 schema:pagination 151-162
17 schema:productId N5a8b61ca201c41fc8c9f3d768f8154a1
18 Na6753e3fa7d54a8fa34a97e2550f6e9d
19 Nca3ad4e317a9418da6e567dd699565b0
20 schema:publisher N1eabc737d31f448998fcd1245be8d53a
21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005416239
22 https://doi.org/10.1007/3-540-57155-8_244
23 schema:sdDatePublished 2019-04-15T22:53
24 schema:sdLicense https://scigraph.springernature.com/explorer/license/
25 schema:sdPublisher N2019e2310f4c48c4812c0903a70b8668
26 schema:url http://link.springer.com/10.1007/3-540-57155-8_244
27 sgo:license sg:explorer/license/
28 sgo:sdDataset chapters
29 rdf:type schema:Chapter
30 N04bbef8092744cc7a2ad937fc3511aef rdf:first N42e38bb2370b46e998793db36072cbe2
31 rdf:rest Naf33bc28223348949badca732584aad7
32 N0db0531719fe421ea3e6a8120b1f789a rdf:first N9a9b48c409424cacaefa7f25a2224fbb
33 rdf:rest N8846258780054e0383135aedc95bb3e5
34 N1eabc737d31f448998fcd1245be8d53a schema:location Berlin, Heidelberg
35 schema:name Springer Berlin Heidelberg
36 rdf:type schema:Organisation
37 N2019e2310f4c48c4812c0903a70b8668 schema:name Springer Nature - SN SciGraph project
38 rdf:type schema:Organization
39 N42e38bb2370b46e998793db36072cbe2 schema:familyName Santoro
40 schema:givenName Nicola
41 rdf:type schema:Person
42 N504924b3aafb4a1696069fb627e723d7 rdf:first sg:person.012154640211.03
43 rdf:rest rdf:nil
44 N5a8b61ca201c41fc8c9f3d768f8154a1 schema:name dimensions_id
45 schema:value pub.1005416239
46 rdf:type schema:PropertyValue
47 N5e49526f0291445498f3b74f3e273c0c rdf:first sg:person.0616310175.56
48 rdf:rest N6387908502e3449cbf41520f39d41d49
49 N6387908502e3449cbf41520f39d41d49 rdf:first sg:person.0616776646.71
50 rdf:rest N504924b3aafb4a1696069fb627e723d7
51 N8846258780054e0383135aedc95bb3e5 rdf:first Ncdbfe176fc74454895b58489e0638ab0
52 rdf:rest N04bbef8092744cc7a2ad937fc3511aef
53 N943f9b92eb4b4e55b41c1281f0925d7f schema:isbn 978-3-540-47918-5
54 978-3-540-57155-1
55 schema:name Algorithms and Data Structures
56 rdf:type schema:Book
57 N9a9b48c409424cacaefa7f25a2224fbb schema:familyName Dehne
58 schema:givenName Frank
59 rdf:type schema:Person
60 Na6753e3fa7d54a8fa34a97e2550f6e9d schema:name doi
61 schema:value 10.1007/3-540-57155-8_244
62 rdf:type schema:PropertyValue
63 Naf33bc28223348949badca732584aad7 rdf:first Nb8198c3688cb4273a8aebdb530eeb249
64 rdf:rest rdf:nil
65 Nb8198c3688cb4273a8aebdb530eeb249 schema:familyName Whitesides
66 schema:givenName Sue
67 rdf:type schema:Person
68 Nca3ad4e317a9418da6e567dd699565b0 schema:name readcube_id
69 schema:value 19ce4d486f1188f2de261467a9e1584eaff1dbb661d1d41fcf8a31ef4b1ca259
70 rdf:type schema:PropertyValue
71 Ncdbfe176fc74454895b58489e0638ab0 schema:familyName Sack
72 schema:givenName Jörg-Rüdiger
73 rdf:type schema:Person
74 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
75 schema:name Information and Computing Sciences
76 rdf:type schema:DefinedTerm
77 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
78 schema:name Computation Theory and Mathematics
79 rdf:type schema:DefinedTerm
80 sg:person.012154640211.03 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
81 schema:familyName Vargiu
82 schema:givenName Francesco
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012154640211.03
84 rdf:type schema:Person
85 sg:person.0616310175.56 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
86 schema:familyName Di Battista
87 schema:givenName Giuseppe
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0616310175.56
89 rdf:type schema:Person
90 sg:person.0616776646.71 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
91 schema:familyName Liotta
92 schema:givenName Giuseppe
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0616776646.71
94 rdf:type schema:Person
95 https://doi.org/10.1016/0304-3975(88)90123-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030081374
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1109/31.34669 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061153032
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1137/0216030 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841976
100 rdf:type schema:CreativeWork
101 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
102 schema:name Dipartimento di Informatica e Sistemistica, Università di Roma “La Sapienza”, via Salaria 113, I-00198 Roma, Italia
103 rdf:type schema:Organization
 




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


...