Planar acyclic oriented graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1989-12

AUTHORS

Carsten Thomassen

ABSTRACT

A plane Hasse representation of an acyclic oriented graph is a drawing of the graph in the Euclidean plane such that all arcs are straight-line segments directed upwards and such that no two arcs cross. We characterize completely those oriented graphs which have a plane Hasse representation such that all faces are bounded by convex polygons. From this we derive the Hasse representation analogue, due to Kelly and Rival of Fary's theorem on straight-line representations of planar graphs and the Kuratowski type theorem of Platt for acyclic oriented graphs with only one source and one sink. Finally, we describe completely those acyclic oriented graphs which have a vertex dominating all other vertices and which have no plane Hasse representation, a problem posed by Trotter. More... »

PAGES

349-361

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "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": "Technical University of Denmark", 
          "id": "https://www.grid.ac/institutes/grid.5170.3", 
          "name": [
            "Mathematical Institute, The Technical University of Denmark, Building 303, DK-2800, Lyngby, Denmark"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Thomassen", 
        "givenName": "Carsten", 
        "id": "sg:person.011431216645.38", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011431216645.38"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0095-8956(80)90083-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016550143"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0095-8956(76)90024-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025374458"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(87)90008-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027243701"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4153/cjm-1975-074-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1072266040"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1989-12", 
    "datePublishedReg": "1989-12-01", 
    "description": "A plane Hasse representation of an acyclic oriented graph is a drawing of the graph in the Euclidean plane such that all arcs are straight-line segments directed upwards and such that no two arcs cross. We characterize completely those oriented graphs which have a plane Hasse representation such that all faces are bounded by convex polygons. From this we derive the Hasse representation analogue, due to Kelly and Rival of Fary's theorem on straight-line representations of planar graphs and the Kuratowski type theorem of Platt for acyclic oriented graphs with only one source and one sink. Finally, we describe completely those acyclic oriented graphs which have a vertex dominating all other vertices and which have no plane Hasse representation, a problem posed by Trotter.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf00353654", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136683", 
        "issn": [
          "0167-8094", 
          "1572-9273"
        ], 
        "name": "Order", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "5"
      }
    ], 
    "name": "Planar acyclic oriented graphs", 
    "pagination": "349-361", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf00353654"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "461f604a22255b92231171a367d8409707f67dd9724337294e384784a5b8adf3"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1014718552"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf00353654", 
      "https://app.dimensions.ai/details/publication/pub.1014718552"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-15T08:50", 
    "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/0000000374_0000000374/records_119732_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/BF00353654"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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/bf00353654 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author N451ec9543fe04770b1823539465d6aec
4 schema:citation https://doi.org/10.1016/0012-365x(87)90008-2
5 https://doi.org/10.1016/0095-8956(76)90024-1
6 https://doi.org/10.1016/0095-8956(80)90083-0
7 https://doi.org/10.4153/cjm-1975-074-0
8 schema:datePublished 1989-12
9 schema:datePublishedReg 1989-12-01
10 schema:description A plane Hasse representation of an acyclic oriented graph is a drawing of the graph in the Euclidean plane such that all arcs are straight-line segments directed upwards and such that no two arcs cross. We characterize completely those oriented graphs which have a plane Hasse representation such that all faces are bounded by convex polygons. From this we derive the Hasse representation analogue, due to Kelly and Rival of Fary's theorem on straight-line representations of planar graphs and the Kuratowski type theorem of Platt for acyclic oriented graphs with only one source and one sink. Finally, we describe completely those acyclic oriented graphs which have a vertex dominating all other vertices and which have no plane Hasse representation, a problem posed by Trotter.
11 schema:genre research_article
12 schema:inLanguage en
13 schema:isAccessibleForFree false
14 schema:isPartOf N3f9d2baaa1144893adf90b8817636389
15 Nfcba8f3a51c948c4a5fb99e07496f9d6
16 sg:journal.1136683
17 schema:name Planar acyclic oriented graphs
18 schema:pagination 349-361
19 schema:productId N22d55f7f8a914a3ca0c7716b3e94b459
20 N238f7f9e53304b46b2cb12004379b89c
21 Na1f8fc428bb54d54bbb2212e72be5f28
22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014718552
23 https://doi.org/10.1007/bf00353654
24 schema:sdDatePublished 2019-04-15T08:50
25 schema:sdLicense https://scigraph.springernature.com/explorer/license/
26 schema:sdPublisher N0860b8f63b29467589fa510f72f2c2cd
27 schema:url http://link.springer.com/10.1007/BF00353654
28 sgo:license sg:explorer/license/
29 sgo:sdDataset articles
30 rdf:type schema:ScholarlyArticle
31 N0860b8f63b29467589fa510f72f2c2cd schema:name Springer Nature - SN SciGraph project
32 rdf:type schema:Organization
33 N22d55f7f8a914a3ca0c7716b3e94b459 schema:name dimensions_id
34 schema:value pub.1014718552
35 rdf:type schema:PropertyValue
36 N238f7f9e53304b46b2cb12004379b89c schema:name readcube_id
37 schema:value 461f604a22255b92231171a367d8409707f67dd9724337294e384784a5b8adf3
38 rdf:type schema:PropertyValue
39 N3f9d2baaa1144893adf90b8817636389 schema:volumeNumber 5
40 rdf:type schema:PublicationVolume
41 N451ec9543fe04770b1823539465d6aec rdf:first sg:person.011431216645.38
42 rdf:rest rdf:nil
43 Na1f8fc428bb54d54bbb2212e72be5f28 schema:name doi
44 schema:value 10.1007/bf00353654
45 rdf:type schema:PropertyValue
46 Nfcba8f3a51c948c4a5fb99e07496f9d6 schema:issueNumber 4
47 rdf:type schema:PublicationIssue
48 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
49 schema:name Information and Computing Sciences
50 rdf:type schema:DefinedTerm
51 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
52 schema:name Information Systems
53 rdf:type schema:DefinedTerm
54 sg:journal.1136683 schema:issn 0167-8094
55 1572-9273
56 schema:name Order
57 rdf:type schema:Periodical
58 sg:person.011431216645.38 schema:affiliation https://www.grid.ac/institutes/grid.5170.3
59 schema:familyName Thomassen
60 schema:givenName Carsten
61 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011431216645.38
62 rdf:type schema:Person
63 https://doi.org/10.1016/0012-365x(87)90008-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027243701
64 rdf:type schema:CreativeWork
65 https://doi.org/10.1016/0095-8956(76)90024-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025374458
66 rdf:type schema:CreativeWork
67 https://doi.org/10.1016/0095-8956(80)90083-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016550143
68 rdf:type schema:CreativeWork
69 https://doi.org/10.4153/cjm-1975-074-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072266040
70 rdf:type schema:CreativeWork
71 https://www.grid.ac/institutes/grid.5170.3 schema:alternateName Technical University of Denmark
72 schema:name Mathematical Institute, The Technical University of Denmark, Building 303, DK-2800, Lyngby, Denmark
73 rdf:type schema:Organization
 




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


...