Drawing plane graphs nicely View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1985-06

AUTHORS

Norishige Chiba, Kazunori Onoguchi, Takao Nishizeki

ABSTRACT

This paper presents two efficient algorithms for drawing plane graphs nicely. Both draw all edges of a graph as straight line segments without crossing lines. The first draws a plane graph “convex” if possible, that is, in a way that every inner face and the complement of the outer face are convex polygons. The second, using the first, produces a pleasing drawing of a given plane graph that satisfies the following property as far as possible: the complements of 3-connected components, together with inner faces and the complement of the outer face, are convex polygons. The running time and storage space of both algorithms are linear in the number of vertices of the graph. More... »

PAGES

187-201

References to SciGraph publications

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "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": "Tohoku University", 
          "id": "https://www.grid.ac/institutes/grid.69566.3a", 
          "name": [
            "Department of Electrical Communications, Faculty of Engineering, Tohoku University, 980, Sendai, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chiba", 
        "givenName": "Norishige", 
        "id": "sg:person.015163452002.91", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015163452002.91"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Tohoku University", 
          "id": "https://www.grid.ac/institutes/grid.69566.3a", 
          "name": [
            "Department of Electrical Communications, Faculty of Engineering, Tohoku University, 980, Sendai, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Onoguchi", 
        "givenName": "Kazunori", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Tohoku University", 
          "id": "https://www.grid.ac/institutes/grid.69566.3a", 
          "name": [
            "Department of Electrical Communications, Faculty of Engineering, Tohoku University, 980, Sendai, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nishizeki", 
        "givenName": "Takao", 
        "id": "sg:person.010464532434.07", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010464532434.07"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf00289576", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004282920", 
          "https://doi.org/10.1007/bf00289576"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "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.1002/spe.4380100706", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018211857"
        ], 
        "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.1016/0022-0000(85)90004-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030929286"
        ], 
        "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.1112/plms/s3-10.1.304", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051445647"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tse.1979.234212", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061787341"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tse.1981.234519", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061787468"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0202012", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841200"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0716027", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062852588"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1985-06", 
    "datePublishedReg": "1985-06-01", 
    "description": "This paper presents two efficient algorithms for drawing plane graphs nicely. Both draw all edges of a graph as straight line segments without crossing lines. The first draws a plane graph \u201cconvex\u201d if possible, that is, in a way that every inner face and the complement of the outer face are convex polygons. The second, using the first, produces a pleasing drawing of a given plane graph that satisfies the following property as far as possible: the complements of 3-connected components, together with inner faces and the complement of the outer face, are convex polygons. The running time and storage space of both algorithms are linear in the number of vertices of the graph.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf00264230", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1133515", 
        "issn": [
          "0001-5903", 
          "1432-0525"
        ], 
        "name": "Acta Informatica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "22"
      }
    ], 
    "name": "Drawing plane graphs nicely", 
    "pagination": "187-201", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "f82ef8db7d7f313152e801cd0143d62cba7053c3bb2f31ff3eec0a3967718d98"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf00264230"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1052102689"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf00264230", 
      "https://app.dimensions.ai/details/publication/pub.1052102689"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T13: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/0000000371_0000000371/records_130797_00000004.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/BF00264230"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

108 TRIPLES      21 PREDICATES      38 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf00264230 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nc0929906e15640d4b2c8917ca3bd7a65
4 schema:citation sg:pub.10.1007/bf00289576
5 https://doi.org/10.1002/spe.4380100706
6 https://doi.org/10.1016/0022-0000(85)90004-2
7 https://doi.org/10.1016/0095-8956(80)90083-0
8 https://doi.org/10.1109/tse.1979.234212
9 https://doi.org/10.1109/tse.1981.234519
10 https://doi.org/10.1112/plms/s3-10.1.304
11 https://doi.org/10.1112/plms/s3-13.1.743
12 https://doi.org/10.1137/0202012
13 https://doi.org/10.1137/0716027
14 https://doi.org/10.1145/321850.321852
15 schema:datePublished 1985-06
16 schema:datePublishedReg 1985-06-01
17 schema:description This paper presents two efficient algorithms for drawing plane graphs nicely. Both draw all edges of a graph as straight line segments without crossing lines. The first draws a plane graph “convex” if possible, that is, in a way that every inner face and the complement of the outer face are convex polygons. The second, using the first, produces a pleasing drawing of a given plane graph that satisfies the following property as far as possible: the complements of 3-connected components, together with inner faces and the complement of the outer face, are convex polygons. The running time and storage space of both algorithms are linear in the number of vertices of the graph.
18 schema:genre research_article
19 schema:inLanguage en
20 schema:isAccessibleForFree false
21 schema:isPartOf N2a5bc608bc2a4c47b8d86ae793cbacc6
22 N789b0bd32c06430991634d3de7f1df4d
23 sg:journal.1133515
24 schema:name Drawing plane graphs nicely
25 schema:pagination 187-201
26 schema:productId N036d08b316274b98a3677790814a78f1
27 N6d5ac278fa2047e88c0d70f71014e2c7
28 Ne047a28d764a4aa8993967f7be36dcc6
29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052102689
30 https://doi.org/10.1007/bf00264230
31 schema:sdDatePublished 2019-04-11T13:50
32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
33 schema:sdPublisher N1710ffc64e4042fdbf8ba98e17fe5ea7
34 schema:url http://link.springer.com/10.1007/BF00264230
35 sgo:license sg:explorer/license/
36 sgo:sdDataset articles
37 rdf:type schema:ScholarlyArticle
38 N036d08b316274b98a3677790814a78f1 schema:name readcube_id
39 schema:value f82ef8db7d7f313152e801cd0143d62cba7053c3bb2f31ff3eec0a3967718d98
40 rdf:type schema:PropertyValue
41 N1710ffc64e4042fdbf8ba98e17fe5ea7 schema:name Springer Nature - SN SciGraph project
42 rdf:type schema:Organization
43 N2a5bc608bc2a4c47b8d86ae793cbacc6 schema:issueNumber 2
44 rdf:type schema:PublicationIssue
45 N36dc423bbc5248b6a4516122ae25caef schema:affiliation https://www.grid.ac/institutes/grid.69566.3a
46 schema:familyName Onoguchi
47 schema:givenName Kazunori
48 rdf:type schema:Person
49 N6d5ac278fa2047e88c0d70f71014e2c7 schema:name dimensions_id
50 schema:value pub.1052102689
51 rdf:type schema:PropertyValue
52 N789b0bd32c06430991634d3de7f1df4d schema:volumeNumber 22
53 rdf:type schema:PublicationVolume
54 Nb398797499414b8cbab64ada6edc5dcc rdf:first N36dc423bbc5248b6a4516122ae25caef
55 rdf:rest Nd5a6b5c7bfdf4cbea4119e9a2481e224
56 Nc0929906e15640d4b2c8917ca3bd7a65 rdf:first sg:person.015163452002.91
57 rdf:rest Nb398797499414b8cbab64ada6edc5dcc
58 Nd5a6b5c7bfdf4cbea4119e9a2481e224 rdf:first sg:person.010464532434.07
59 rdf:rest rdf:nil
60 Ne047a28d764a4aa8993967f7be36dcc6 schema:name doi
61 schema:value 10.1007/bf00264230
62 rdf:type schema:PropertyValue
63 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
64 schema:name Information and Computing Sciences
65 rdf:type schema:DefinedTerm
66 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
67 schema:name Computation Theory and Mathematics
68 rdf:type schema:DefinedTerm
69 sg:journal.1133515 schema:issn 0001-5903
70 1432-0525
71 schema:name Acta Informatica
72 rdf:type schema:Periodical
73 sg:person.010464532434.07 schema:affiliation https://www.grid.ac/institutes/grid.69566.3a
74 schema:familyName Nishizeki
75 schema:givenName Takao
76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010464532434.07
77 rdf:type schema:Person
78 sg:person.015163452002.91 schema:affiliation https://www.grid.ac/institutes/grid.69566.3a
79 schema:familyName Chiba
80 schema:givenName Norishige
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015163452002.91
82 rdf:type schema:Person
83 sg:pub.10.1007/bf00289576 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004282920
84 https://doi.org/10.1007/bf00289576
85 rdf:type schema:CreativeWork
86 https://doi.org/10.1002/spe.4380100706 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018211857
87 rdf:type schema:CreativeWork
88 https://doi.org/10.1016/0022-0000(85)90004-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030929286
89 rdf:type schema:CreativeWork
90 https://doi.org/10.1016/0095-8956(80)90083-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016550143
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1109/tse.1979.234212 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061787341
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1109/tse.1981.234519 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061787468
95 rdf:type schema:CreativeWork
96 https://doi.org/10.1112/plms/s3-10.1.304 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051445647
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1112/plms/s3-13.1.743 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040536272
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1137/0202012 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841200
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1137/0716027 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062852588
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1145/321850.321852 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023277958
105 rdf:type schema:CreativeWork
106 https://www.grid.ac/institutes/grid.69566.3a schema:alternateName Tohoku University
107 schema:name Department of Electrical Communications, Faculty of Engineering, Tohoku University, 980, Sendai, Japan
108 rdf:type schema:Organization
 




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


...