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 Nfe64f30a5fa047968e90f44df5466678
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 N8e23d10ec4504ef1934398fd852cf03a
15 Nd7facc36aa1140a5889e39e8d178cc1d
16 sg:journal.1136683
17 schema:name Planar acyclic oriented graphs
18 schema:pagination 349-361
19 schema:productId N1c780701a7b244f5bb598d10a0ef1648
20 Nda8b207e6e634a57aa5311c9647e1b68
21 Ndfb32889467c40168bbf9f690901f51a
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 Ndb852fb1757f4928ad2609a8e8e90a80
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 N1c780701a7b244f5bb598d10a0ef1648 schema:name readcube_id
32 schema:value 461f604a22255b92231171a367d8409707f67dd9724337294e384784a5b8adf3
33 rdf:type schema:PropertyValue
34 N8e23d10ec4504ef1934398fd852cf03a schema:issueNumber 4
35 rdf:type schema:PublicationIssue
36 Nd7facc36aa1140a5889e39e8d178cc1d schema:volumeNumber 5
37 rdf:type schema:PublicationVolume
38 Nda8b207e6e634a57aa5311c9647e1b68 schema:name doi
39 schema:value 10.1007/bf00353654
40 rdf:type schema:PropertyValue
41 Ndb852fb1757f4928ad2609a8e8e90a80 schema:name Springer Nature - SN SciGraph project
42 rdf:type schema:Organization
43 Ndfb32889467c40168bbf9f690901f51a schema:name dimensions_id
44 schema:value pub.1014718552
45 rdf:type schema:PropertyValue
46 Nfe64f30a5fa047968e90f44df5466678 rdf:first sg:person.011431216645.38
47 rdf:rest rdf:nil
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)


...