At most single-bend embeddings of cubic graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1994-06

AUTHORS

Liu Yanpei, P. Marchioro, R. Petreschi

ABSTRACT

This paper provides the complete proof of the fact that any planar cubic graph is at most single-bend embeddable except for the tetrahedron. AnO(n) amortized time algorithm for drawing an at most single-bend embedding of a cubic graph is also presented, wheren is the number of vertices of the graph. Furthermore, it is proved that the minimum of the total number of bends in an at most single-bend embedding of a cubic graph of ordern is less than or equal to 0.5n+1. This result is the best possible. More... »

PAGES

127-142

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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": [
            "Institute of Applied Mathematics, Academia Sinica, 100080, Beijing", 
            "Department of Mathematics, University of Rome \u201cLa Sapienza\u201d, Rome, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yanpei", 
        "givenName": "Liu", 
        "id": "sg:person.011630314073.65", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011630314073.65"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Institute of Applied Mathematics, Academia Sinica, 100080, Beijing", 
            "Department of Mathematics, University of Rome \u201cLa Sapienza\u201d, Rome, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Marchioro", 
        "givenName": "P.", 
        "id": "sg:person.015045661577.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015045661577.05"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Institute of Applied Mathematics, Academia Sinica, 100080, Beijing", 
            "Department of Mathematics, University of Rome \u201cLa Sapienza\u201d, Rome, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Petreschi", 
        "givenName": "R.", 
        "id": "sg:person.011402427702.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0304-3975(76)90086-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035496339"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1994-06", 
    "datePublishedReg": "1994-06-01", 
    "description": "This paper provides the complete proof of the fact that any planar cubic graph is at most single-bend embeddable except for the tetrahedron. AnO(n) amortized time algorithm for drawing an at most single-bend embedding of a cubic graph is also presented, wheren is the number of vertices of the graph. Furthermore, it is proved that the minimum of the total number of bends in an at most single-bend embedding of a cubic graph of ordern is less than or equal to 0.5n+1. This result is the best possible.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf02662066", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1327538", 
        "issn": [
          "2152-7385", 
          "2152-7393"
        ], 
        "name": "Applied Mathematics", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "9"
      }
    ], 
    "name": "At most single-bend embeddings of cubic graphs", 
    "pagination": "127-142", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "c7c4b61b9b0a7b2fde4221fa76a2029306a607d81069dff7ab89619448de5b41"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf02662066"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1041936795"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf02662066", 
      "https://app.dimensions.ai/details/publication/pub.1041936795"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T13:27", 
    "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/0000000370_0000000370/records_46737_00000002.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2FBF02662066"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

79 TRIPLES      21 PREDICATES      28 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf02662066 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N5849785588c243049265ea8459f7345d
4 schema:citation https://doi.org/10.1016/0304-3975(76)90086-4
5 schema:datePublished 1994-06
6 schema:datePublishedReg 1994-06-01
7 schema:description This paper provides the complete proof of the fact that any planar cubic graph is at most single-bend embeddable except for the tetrahedron. AnO(n) amortized time algorithm for drawing an at most single-bend embedding of a cubic graph is also presented, wheren is the number of vertices of the graph. Furthermore, it is proved that the minimum of the total number of bends in an at most single-bend embedding of a cubic graph of ordern is less than or equal to 0.5n+1. This result is the best possible.
8 schema:genre research_article
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N9b50db5fcb444dbfacc1fba83401524c
12 Nb4040d55bcd44da49ac02b2d0d8b358f
13 sg:journal.1327538
14 schema:name At most single-bend embeddings of cubic graphs
15 schema:pagination 127-142
16 schema:productId N806e79e5418e401883c8c338df4785da
17 Nd5d8a8745bd74acaa017d7516c9399f8
18 Ne54170c38e3d4c5699e89ad3a9bc5d9d
19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041936795
20 https://doi.org/10.1007/bf02662066
21 schema:sdDatePublished 2019-04-11T13:27
22 schema:sdLicense https://scigraph.springernature.com/explorer/license/
23 schema:sdPublisher N69c739b78ecf4b609a48b8fd738f9825
24 schema:url http://link.springer.com/10.1007%2FBF02662066
25 sgo:license sg:explorer/license/
26 sgo:sdDataset articles
27 rdf:type schema:ScholarlyArticle
28 N5849785588c243049265ea8459f7345d rdf:first sg:person.011630314073.65
29 rdf:rest N6eadabb5d1124956a2e529dd35aa8c28
30 N662976f5cea24425a7ea17d9a5d91ab7 rdf:first sg:person.011402427702.78
31 rdf:rest rdf:nil
32 N69c739b78ecf4b609a48b8fd738f9825 schema:name Springer Nature - SN SciGraph project
33 rdf:type schema:Organization
34 N6eadabb5d1124956a2e529dd35aa8c28 rdf:first sg:person.015045661577.05
35 rdf:rest N662976f5cea24425a7ea17d9a5d91ab7
36 N806e79e5418e401883c8c338df4785da schema:name dimensions_id
37 schema:value pub.1041936795
38 rdf:type schema:PropertyValue
39 N9b50db5fcb444dbfacc1fba83401524c schema:volumeNumber 9
40 rdf:type schema:PublicationVolume
41 Nb4040d55bcd44da49ac02b2d0d8b358f schema:issueNumber 2
42 rdf:type schema:PublicationIssue
43 Nd5d8a8745bd74acaa017d7516c9399f8 schema:name doi
44 schema:value 10.1007/bf02662066
45 rdf:type schema:PropertyValue
46 Ne54170c38e3d4c5699e89ad3a9bc5d9d schema:name readcube_id
47 schema:value c7c4b61b9b0a7b2fde4221fa76a2029306a607d81069dff7ab89619448de5b41
48 rdf:type schema:PropertyValue
49 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
50 schema:name Information and Computing Sciences
51 rdf:type schema:DefinedTerm
52 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
53 schema:name Computation Theory and Mathematics
54 rdf:type schema:DefinedTerm
55 sg:journal.1327538 schema:issn 2152-7385
56 2152-7393
57 schema:name Applied Mathematics
58 rdf:type schema:Periodical
59 sg:person.011402427702.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
60 schema:familyName Petreschi
61 schema:givenName R.
62 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
63 rdf:type schema:Person
64 sg:person.011630314073.65 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
65 schema:familyName Yanpei
66 schema:givenName Liu
67 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011630314073.65
68 rdf:type schema:Person
69 sg:person.015045661577.05 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
70 schema:familyName Marchioro
71 schema:givenName P.
72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015045661577.05
73 rdf:type schema:Person
74 https://doi.org/10.1016/0304-3975(76)90086-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035496339
75 rdf:type schema:CreativeWork
76 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
77 schema:name Department of Mathematics, University of Rome “La Sapienza”, Rome, Italy
78 Institute of Applied Mathematics, Academia Sinica, 100080, Beijing
79 rdf:type schema:Organization
 




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


...