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 N97a20c3d5bdd495da4d1d1f1f80840bf
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 N8df7fd4bebe94fad84437bbfae663c81
11 schema:genre chapter
12 schema:inLanguage en
13 schema:isAccessibleForFree false
14 schema:isPartOf N5c89706b98f148e78c674264b37dcbf7
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 N6976b4fa50264283b6befa095e4be5af
18 N8da6d4170577432a844448527e9905ec
19 Nc6d2e4fd06ed46fe9c6a10ded16543c0
20 schema:publisher Nd42c74cac4854ac7ba591ed06648fc7e
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 Ned6f528d5da2470491b929fb7b1dd514
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 N1dc6e40b95994eb9a4c0a0ef180ffbd5 schema:familyName Dehne
31 schema:givenName Frank
32 rdf:type schema:Person
33 N24bf1488d4804bacbf722179f47fba7d rdf:first N73a08d1948f547d88f91a316ae163cff
34 rdf:rest Nd945da9e860448c1989b95e683ca23d9
35 N53a56075a1984976871989edb39c2555 rdf:first sg:person.0616776646.71
36 rdf:rest Nc2e714fd13af4717a7467f8af16911bf
37 N5c89706b98f148e78c674264b37dcbf7 schema:isbn 978-3-540-47918-5
38 978-3-540-57155-1
39 schema:name Algorithms and Data Structures
40 rdf:type schema:Book
41 N6976b4fa50264283b6befa095e4be5af schema:name dimensions_id
42 schema:value pub.1005416239
43 rdf:type schema:PropertyValue
44 N73a08d1948f547d88f91a316ae163cff schema:familyName Santoro
45 schema:givenName Nicola
46 rdf:type schema:Person
47 N8d208265e7fa464fa3f14ca367dbb69a schema:familyName Sack
48 schema:givenName Jörg-Rüdiger
49 rdf:type schema:Person
50 N8da6d4170577432a844448527e9905ec schema:name readcube_id
51 schema:value 19ce4d486f1188f2de261467a9e1584eaff1dbb661d1d41fcf8a31ef4b1ca259
52 rdf:type schema:PropertyValue
53 N8df7fd4bebe94fad84437bbfae663c81 rdf:first N1dc6e40b95994eb9a4c0a0ef180ffbd5
54 rdf:rest Ne1aeeb076e9d401c93680a653af98e71
55 N97a20c3d5bdd495da4d1d1f1f80840bf rdf:first sg:person.0616310175.56
56 rdf:rest N53a56075a1984976871989edb39c2555
57 Nbb60e318235e4647a7d322b7878b5080 schema:familyName Whitesides
58 schema:givenName Sue
59 rdf:type schema:Person
60 Nc2e714fd13af4717a7467f8af16911bf rdf:first sg:person.012154640211.03
61 rdf:rest rdf:nil
62 Nc6d2e4fd06ed46fe9c6a10ded16543c0 schema:name doi
63 schema:value 10.1007/3-540-57155-8_244
64 rdf:type schema:PropertyValue
65 Nd42c74cac4854ac7ba591ed06648fc7e schema:location Berlin, Heidelberg
66 schema:name Springer Berlin Heidelberg
67 rdf:type schema:Organisation
68 Nd945da9e860448c1989b95e683ca23d9 rdf:first Nbb60e318235e4647a7d322b7878b5080
69 rdf:rest rdf:nil
70 Ne1aeeb076e9d401c93680a653af98e71 rdf:first N8d208265e7fa464fa3f14ca367dbb69a
71 rdf:rest N24bf1488d4804bacbf722179f47fba7d
72 Ned6f528d5da2470491b929fb7b1dd514 schema:name Springer Nature - SN SciGraph project
73 rdf:type schema:Organization
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)


...