Boolean approach to planar embeddings of a graph View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1989-03

AUTHORS

Liu Yanpei

ABSTRACT

The purpose of this paper which is a sequel of “ Boolean planarity characterization of graphs ” [9] is to show the following results.Both of the problems of testing the planarity of graphs and embedding a planar graph into the plane are equivalent to finding a spanning tree in another graph whose order and size are bounded by a linear function of the order and the size of the original graph, respectively.The number of topologically non-equivalent planar embeddings of a Hamiltonian planar graphG is τ(G)=2c(H)−1, wherec (H) is the number of the components of the graphH which is related toG. Both of the problems of testing the planarity of graphs and embedding a planar graph into the plane are equivalent to finding a spanning tree in another graph whose order and size are bounded by a linear function of the order and the size of the original graph, respectively. The number of topologically non-equivalent planar embeddings of a Hamiltonian planar graphG is τ(G)=2c(H)−1, wherec (H) is the number of the components of the graphH which is related toG. More... »

PAGES

64-79

References to SciGraph publications

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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": "Rutgers University", 
          "id": "https://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "RUTCOR, Rutgers University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yanpei", 
        "givenName": "Liu", 
        "id": "sg:person.016630734411.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016630734411.30"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/s0021-9800(70)80007-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012037191"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/321850.321852", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023277958"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1050993949", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-85823-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050993949", 
          "https://doi.org/10.1007/978-3-642-85823-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-85823-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050993949", 
          "https://doi.org/10.1007/978-3-642-85823-9"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1989-03", 
    "datePublishedReg": "1989-03-01", 
    "description": "The purpose of this paper which is a sequel of \u201c Boolean planarity characterization of graphs \u201d [9] is to show the following results.Both of the problems of testing the planarity of graphs and embedding a planar graph into the plane are equivalent to finding a spanning tree in another graph whose order and size are bounded by a linear function of the order and the size of the original graph, respectively.The number of topologically non-equivalent planar embeddings of a Hamiltonian planar graphG is \u03c4(G)=2c(H)\u22121, wherec (H) is the number of the components of the graphH which is related toG. Both of the problems of testing the planarity of graphs and embedding a planar graph into the plane are equivalent to finding a spanning tree in another graph whose order and size are bounded by a linear function of the order and the size of the original graph, respectively. The number of topologically non-equivalent planar embeddings of a Hamiltonian planar graphG is \u03c4(G)=2c(H)\u22121, wherec (H) is the number of the components of the graphH which is related toG.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf02107624", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1040372", 
        "issn": [
          "1439-8516", 
          "1439-7617"
        ], 
        "name": "Acta Mathematica Sinica, English Series", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "5"
      }
    ], 
    "name": "Boolean approach to planar embeddings of a graph", 
    "pagination": "64-79", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "79ef771a587009caaa0886d09bd1cee319767727af11443df6a5c391f8223ed8"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf02107624"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1025594661"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf02107624", 
      "https://app.dimensions.ai/details/publication/pub.1025594661"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T12:03", 
    "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/0000000360_0000000360/records_118306_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/BF02107624"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

73 TRIPLES      21 PREDICATES      31 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf02107624 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N1eb5f40d70704301b449bbf9f793d158
4 schema:citation sg:pub.10.1007/978-3-642-85823-9
5 https://app.dimensions.ai/details/publication/pub.1050993949
6 https://doi.org/10.1016/s0021-9800(70)80007-2
7 https://doi.org/10.1145/321850.321852
8 schema:datePublished 1989-03
9 schema:datePublishedReg 1989-03-01
10 schema:description The purpose of this paper which is a sequel of “ Boolean planarity characterization of graphs ” [9] is to show the following results.Both of the problems of testing the planarity of graphs and embedding a planar graph into the plane are equivalent to finding a spanning tree in another graph whose order and size are bounded by a linear function of the order and the size of the original graph, respectively.The number of topologically non-equivalent planar embeddings of a Hamiltonian planar graphG is τ(G)=2c(H)−1, wherec (H) is the number of the components of the graphH which is related toG. Both of the problems of testing the planarity of graphs and embedding a planar graph into the plane are equivalent to finding a spanning tree in another graph whose order and size are bounded by a linear function of the order and the size of the original graph, respectively. The number of topologically non-equivalent planar embeddings of a Hamiltonian planar graphG is τ(G)=2c(H)−1, wherec (H) is the number of the components of the graphH which is related toG.
11 schema:genre research_article
12 schema:inLanguage en
13 schema:isAccessibleForFree false
14 schema:isPartOf N45b4f4c4609b47518aa0c505880118a5
15 N85a63f6cc04c4717962811b95d14fa8e
16 sg:journal.1040372
17 schema:name Boolean approach to planar embeddings of a graph
18 schema:pagination 64-79
19 schema:productId N17df9bd58d57456da9a7f39ce1e8dfe3
20 N8448277b8d2a4d95b3c03236fe7a5c61
21 Nd9cc033489c14e58b55cda41820890d3
22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025594661
23 https://doi.org/10.1007/bf02107624
24 schema:sdDatePublished 2019-04-11T12:03
25 schema:sdLicense https://scigraph.springernature.com/explorer/license/
26 schema:sdPublisher N6d9d19ea1f454a1596114972f0f6b428
27 schema:url http://link.springer.com/10.1007/BF02107624
28 sgo:license sg:explorer/license/
29 sgo:sdDataset articles
30 rdf:type schema:ScholarlyArticle
31 N17df9bd58d57456da9a7f39ce1e8dfe3 schema:name doi
32 schema:value 10.1007/bf02107624
33 rdf:type schema:PropertyValue
34 N1eb5f40d70704301b449bbf9f793d158 rdf:first sg:person.016630734411.30
35 rdf:rest rdf:nil
36 N45b4f4c4609b47518aa0c505880118a5 schema:issueNumber 1
37 rdf:type schema:PublicationIssue
38 N6d9d19ea1f454a1596114972f0f6b428 schema:name Springer Nature - SN SciGraph project
39 rdf:type schema:Organization
40 N8448277b8d2a4d95b3c03236fe7a5c61 schema:name dimensions_id
41 schema:value pub.1025594661
42 rdf:type schema:PropertyValue
43 N85a63f6cc04c4717962811b95d14fa8e schema:volumeNumber 5
44 rdf:type schema:PublicationVolume
45 Nd9cc033489c14e58b55cda41820890d3 schema:name readcube_id
46 schema:value 79ef771a587009caaa0886d09bd1cee319767727af11443df6a5c391f8223ed8
47 rdf:type schema:PropertyValue
48 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
49 schema:name Mathematical Sciences
50 rdf:type schema:DefinedTerm
51 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
52 schema:name Pure Mathematics
53 rdf:type schema:DefinedTerm
54 sg:journal.1040372 schema:issn 1439-7617
55 1439-8516
56 schema:name Acta Mathematica Sinica, English Series
57 rdf:type schema:Periodical
58 sg:person.016630734411.30 schema:affiliation https://www.grid.ac/institutes/grid.430387.b
59 schema:familyName Yanpei
60 schema:givenName Liu
61 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016630734411.30
62 rdf:type schema:Person
63 sg:pub.10.1007/978-3-642-85823-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050993949
64 https://doi.org/10.1007/978-3-642-85823-9
65 rdf:type schema:CreativeWork
66 https://app.dimensions.ai/details/publication/pub.1050993949 schema:CreativeWork
67 https://doi.org/10.1016/s0021-9800(70)80007-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012037191
68 rdf:type schema:CreativeWork
69 https://doi.org/10.1145/321850.321852 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023277958
70 rdf:type schema:CreativeWork
71 https://www.grid.ac/institutes/grid.430387.b schema:alternateName Rutgers University
72 schema:name RUTCOR, Rutgers University, USA
73 rdf:type schema:Organization
 




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


...