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 N45cbf3a78d15469fb09240198758d01b
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 N0f716cf2aa184c968c8a047506f3dc10
15 N5336e959725f4d53a0f1ce59d8d4915c
16 sg:journal.1040372
17 schema:name Boolean approach to planar embeddings of a graph
18 schema:pagination 64-79
19 schema:productId N413a8e73241d473c94fe05497a09b414
20 N5553a4f0540e44c8be6aa9952c13d266
21 Nec3b3c57d95447b6b4833fc58d13468b
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 N54683d85936046949c89f8677eaf4a8a
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 N0f716cf2aa184c968c8a047506f3dc10 schema:volumeNumber 5
32 rdf:type schema:PublicationVolume
33 N413a8e73241d473c94fe05497a09b414 schema:name dimensions_id
34 schema:value pub.1025594661
35 rdf:type schema:PropertyValue
36 N45cbf3a78d15469fb09240198758d01b rdf:first sg:person.016630734411.30
37 rdf:rest rdf:nil
38 N5336e959725f4d53a0f1ce59d8d4915c schema:issueNumber 1
39 rdf:type schema:PublicationIssue
40 N54683d85936046949c89f8677eaf4a8a schema:name Springer Nature - SN SciGraph project
41 rdf:type schema:Organization
42 N5553a4f0540e44c8be6aa9952c13d266 schema:name readcube_id
43 schema:value 79ef771a587009caaa0886d09bd1cee319767727af11443df6a5c391f8223ed8
44 rdf:type schema:PropertyValue
45 Nec3b3c57d95447b6b4833fc58d13468b 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)


...