Rectilinear planar layouts and bipolar orientations of planar graphs View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1986-12

AUTHORS

Pierre Rosenstiehl, Robert E. Tarjan

ABSTRACT

We propose a linear-time algorithm for generating a planar layout of a planar graph. Each vertex is represented by a horizontal line segment and each edge by a vertical line segment. All endpoints of the segments have integer coordinates. The total space occupied by the layout is at mostn by at most 2n–4. Our algorithm, a variant of one by Otten and van Wijk, generally produces a more compact layout than theirs and allows the dual of the graph to be laid out in an interlocking way. The algorithm is based on the concept of abipolar orientation. We discuss relationships among the bipolar orientations of a planar graph. More... »

PAGES

343-353

References to SciGraph publications

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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": {
          "name": [
            "Centre de Mathematique Sociale, Paris, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rosenstiehl", 
        "givenName": "Pierre", 
        "id": "sg:person.014766674655.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014766674655.01"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Alcatel-Lucent (United States)", 
          "id": "https://www.grid.ac/institutes/grid.421036.2", 
          "name": [
            "Computer Science Department, Princeton University, 08544, Princeton, NJ, USA", 
            "AT&T Bell Laboratories, 07974, Murray Hill, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tarjan", 
        "givenName": "Robert E.", 
        "id": "sg:person.014142465473.44", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014142465473.44"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf02253293", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018365863", 
          "https://doi.org/10.1007/bf02253293"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02253293", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018365863", 
          "https://doi.org/10.1007/bf02253293"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/321850.321852", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023277958"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1111/j.1749-6632.1989.tb22470.x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023776586"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0022-0000(76)80045-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030334487"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(76)90086-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035496339"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1112/plms/s3-13.1.743", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040536272"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(83)90128-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041600793"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0203006", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841220"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1986-12", 
    "datePublishedReg": "1986-12-01", 
    "description": "We propose a linear-time algorithm for generating a planar layout of a planar graph. Each vertex is represented by a horizontal line segment and each edge by a vertical line segment. All endpoints of the segments have integer coordinates. The total space occupied by the layout is at mostn by at most 2n\u20134. Our algorithm, a variant of one by Otten and van Wijk, generally produces a more compact layout than theirs and allows the dual of the graph to be laid out in an interlocking way. The algorithm is based on the concept of abipolar orientation. We discuss relationships among the bipolar orientations of a planar graph.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf02187706", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1043660", 
        "issn": [
          "0179-5376", 
          "1432-0444"
        ], 
        "name": "Discrete & Computational Geometry", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "1"
      }
    ], 
    "name": "Rectilinear planar layouts and bipolar orientations of planar graphs", 
    "pagination": "343-353", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "2a4ffa50146dd183be520ec5966504c1ca5409b41ad1c1b755ca03972bb8f49a"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf02187706"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1008881195"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf02187706", 
      "https://app.dimensions.ai/details/publication/pub.1008881195"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T13:07", 
    "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/0000000367_0000000367/records_88222_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2FBF02187706"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

96 TRIPLES      21 PREDICATES      35 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf02187706 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N696597ac8d374bdeb87a15af26324e6a
4 schema:citation sg:pub.10.1007/bf02253293
5 https://doi.org/10.1016/0012-365x(83)90128-0
6 https://doi.org/10.1016/0304-3975(76)90086-4
7 https://doi.org/10.1016/s0022-0000(76)80045-1
8 https://doi.org/10.1111/j.1749-6632.1989.tb22470.x
9 https://doi.org/10.1112/plms/s3-13.1.743
10 https://doi.org/10.1137/0203006
11 https://doi.org/10.1145/321850.321852
12 schema:datePublished 1986-12
13 schema:datePublishedReg 1986-12-01
14 schema:description We propose a linear-time algorithm for generating a planar layout of a planar graph. Each vertex is represented by a horizontal line segment and each edge by a vertical line segment. All endpoints of the segments have integer coordinates. The total space occupied by the layout is at mostn by at most 2n–4. Our algorithm, a variant of one by Otten and van Wijk, generally produces a more compact layout than theirs and allows the dual of the graph to be laid out in an interlocking way. The algorithm is based on the concept of abipolar orientation. We discuss relationships among the bipolar orientations of a planar graph.
15 schema:genre research_article
16 schema:inLanguage en
17 schema:isAccessibleForFree true
18 schema:isPartOf N13fb9fedc1c942b2a81a774dbcdd1608
19 N9a745602ea48447281277c8236676de0
20 sg:journal.1043660
21 schema:name Rectilinear planar layouts and bipolar orientations of planar graphs
22 schema:pagination 343-353
23 schema:productId N8b7e570cf8ea4a5ea505f7b82b86086c
24 Nb1a63370822043ed8c9d4936a5f080b8
25 Nd06edb46a6234ce0a7191823aef9ce6d
26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008881195
27 https://doi.org/10.1007/bf02187706
28 schema:sdDatePublished 2019-04-11T13:07
29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
30 schema:sdPublisher Nb7cc621aad2549f9b14e526000fd6093
31 schema:url https://link.springer.com/10.1007%2FBF02187706
32 sgo:license sg:explorer/license/
33 sgo:sdDataset articles
34 rdf:type schema:ScholarlyArticle
35 N13e583e124a340ab85079a044032c2cc schema:name Centre de Mathematique Sociale, Paris, France
36 rdf:type schema:Organization
37 N13fb9fedc1c942b2a81a774dbcdd1608 schema:issueNumber 4
38 rdf:type schema:PublicationIssue
39 N696597ac8d374bdeb87a15af26324e6a rdf:first sg:person.014766674655.01
40 rdf:rest N8e0263e22a7344af8d8c4ed7d8185f9a
41 N8b7e570cf8ea4a5ea505f7b82b86086c schema:name readcube_id
42 schema:value 2a4ffa50146dd183be520ec5966504c1ca5409b41ad1c1b755ca03972bb8f49a
43 rdf:type schema:PropertyValue
44 N8e0263e22a7344af8d8c4ed7d8185f9a rdf:first sg:person.014142465473.44
45 rdf:rest rdf:nil
46 N9a745602ea48447281277c8236676de0 schema:volumeNumber 1
47 rdf:type schema:PublicationVolume
48 Nb1a63370822043ed8c9d4936a5f080b8 schema:name dimensions_id
49 schema:value pub.1008881195
50 rdf:type schema:PropertyValue
51 Nb7cc621aad2549f9b14e526000fd6093 schema:name Springer Nature - SN SciGraph project
52 rdf:type schema:Organization
53 Nd06edb46a6234ce0a7191823aef9ce6d schema:name doi
54 schema:value 10.1007/bf02187706
55 rdf:type schema:PropertyValue
56 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
57 schema:name Mathematical Sciences
58 rdf:type schema:DefinedTerm
59 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
60 schema:name Pure Mathematics
61 rdf:type schema:DefinedTerm
62 sg:journal.1043660 schema:issn 0179-5376
63 1432-0444
64 schema:name Discrete & Computational Geometry
65 rdf:type schema:Periodical
66 sg:person.014142465473.44 schema:affiliation https://www.grid.ac/institutes/grid.421036.2
67 schema:familyName Tarjan
68 schema:givenName Robert E.
69 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014142465473.44
70 rdf:type schema:Person
71 sg:person.014766674655.01 schema:affiliation N13e583e124a340ab85079a044032c2cc
72 schema:familyName Rosenstiehl
73 schema:givenName Pierre
74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014766674655.01
75 rdf:type schema:Person
76 sg:pub.10.1007/bf02253293 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018365863
77 https://doi.org/10.1007/bf02253293
78 rdf:type schema:CreativeWork
79 https://doi.org/10.1016/0012-365x(83)90128-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041600793
80 rdf:type schema:CreativeWork
81 https://doi.org/10.1016/0304-3975(76)90086-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035496339
82 rdf:type schema:CreativeWork
83 https://doi.org/10.1016/s0022-0000(76)80045-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030334487
84 rdf:type schema:CreativeWork
85 https://doi.org/10.1111/j.1749-6632.1989.tb22470.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1023776586
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1112/plms/s3-13.1.743 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040536272
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1137/0203006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841220
90 rdf:type schema:CreativeWork
91 https://doi.org/10.1145/321850.321852 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023277958
92 rdf:type schema:CreativeWork
93 https://www.grid.ac/institutes/grid.421036.2 schema:alternateName Alcatel-Lucent (United States)
94 schema:name AT&T Bell Laboratories, 07974, Murray Hill, NJ, USA
95 Computer Science Department, Princeton University, 08544, Princeton, NJ, USA
96 rdf:type schema:Organization
 




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


...