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 N306a238aacb04df58605866937289101
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 N0f437ff0a23b4e1d9697cc50df12a0d0
15 N67e6b26455534c5481d01eb31e24e443
16 sg:journal.1040372
17 schema:name Boolean approach to planar embeddings of a graph
18 schema:pagination 64-79
19 schema:productId N1c443e738ee541389cc01f2266cb90e3
20 N272073e86735443092f088ce60f3876f
21 N791145ba464d4e26a81a541e70f7c370
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 N53ef62980efd4cdfa19466ef621e20e5
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 N0f437ff0a23b4e1d9697cc50df12a0d0 schema:issueNumber 1
32 rdf:type schema:PublicationIssue
33 N1c443e738ee541389cc01f2266cb90e3 schema:name dimensions_id
34 schema:value pub.1025594661
35 rdf:type schema:PropertyValue
36 N272073e86735443092f088ce60f3876f schema:name readcube_id
37 schema:value 79ef771a587009caaa0886d09bd1cee319767727af11443df6a5c391f8223ed8
38 rdf:type schema:PropertyValue
39 N306a238aacb04df58605866937289101 rdf:first sg:person.016630734411.30
40 rdf:rest rdf:nil
41 N53ef62980efd4cdfa19466ef621e20e5 schema:name Springer Nature - SN SciGraph project
42 rdf:type schema:Organization
43 N67e6b26455534c5481d01eb31e24e443 schema:volumeNumber 5
44 rdf:type schema:PublicationVolume
45 N791145ba464d4e26a81a541e70f7c370 schema:name doi
46 schema:value 10.1007/bf02107624
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)


...