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

  • 1983-01. The complexity of drawing trees nicely in ACTA INFORMATICA
  • 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 N2f7a1db24e5e4893bbae5268af57c1f6
    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 N009fc493612749668daddfe20b30f3d6
    22 N34324c03c9c54cfca54498982b92be63
    23 sg:journal.1133515
    24 schema:name Drawing plane graphs nicely
    25 schema:pagination 187-201
    26 schema:productId N79b8861a9fcd42d8b95d0d43bc9adf03
    27 Na92e009bc2064df39eba4088dd2bf1fe
    28 Nef984cc8319a4ec082269ff26084c946
    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 Nf7c464fc9a754ccba21a7fecf0ed2d1f
    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 N009fc493612749668daddfe20b30f3d6 schema:volumeNumber 22
    39 rdf:type schema:PublicationVolume
    40 N2f7a1db24e5e4893bbae5268af57c1f6 rdf:first sg:person.015163452002.91
    41 rdf:rest Nbd5ac9e7db2a4dc19f03731f8d64c505
    42 N34324c03c9c54cfca54498982b92be63 schema:issueNumber 2
    43 rdf:type schema:PublicationIssue
    44 N7189b81c0711416a8810618d3d2ba30f rdf:first sg:person.010464532434.07
    45 rdf:rest rdf:nil
    46 N79b8861a9fcd42d8b95d0d43bc9adf03 schema:name dimensions_id
    47 schema:value pub.1052102689
    48 rdf:type schema:PropertyValue
    49 Na92e009bc2064df39eba4088dd2bf1fe schema:name readcube_id
    50 schema:value f82ef8db7d7f313152e801cd0143d62cba7053c3bb2f31ff3eec0a3967718d98
    51 rdf:type schema:PropertyValue
    52 Nbd5ac9e7db2a4dc19f03731f8d64c505 rdf:first Ncf3863f3d5f2405ea4f82edc827c3b68
    53 rdf:rest N7189b81c0711416a8810618d3d2ba30f
    54 Ncf3863f3d5f2405ea4f82edc827c3b68 schema:affiliation https://www.grid.ac/institutes/grid.69566.3a
    55 schema:familyName Onoguchi
    56 schema:givenName Kazunori
    57 rdf:type schema:Person
    58 Nef984cc8319a4ec082269ff26084c946 schema:name doi
    59 schema:value 10.1007/bf00264230
    60 rdf:type schema:PropertyValue
    61 Nf7c464fc9a754ccba21a7fecf0ed2d1f schema:name Springer Nature - SN SciGraph project
    62 rdf:type schema:Organization
    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)


    ...