How to draw a planar graph on a grid View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1990-03

AUTHORS

H. De Fraysseix, J. Pach, R. Pollack

ABSTRACT

Answering a question of Rosenstiehl and Tarjan, we show that every plane graph withn vertices has a Fáry embedding (i.e., straight-line embedding) on the 2n−4 byn−2 grid and provide anO(n) space,O(n logn) time algorithm to effect this embedding. The grid size is asymptotically optimal and it had been previously unknown whether one can always find a polynomial sized grid to support such an embedding. On the other hand we show that any setF, which can support a Fáry embedding of every planar graph of sizen, has cardinality at leastn+(1−o(1))√n which settles a problem of Mohar. More... »

PAGES

41-51

References to SciGraph publications

  • 1986-12. Rectilinear planar layouts and bipolar orientations of planar graphs in DISCRETE & COMPUTATIONAL GEOMETRY
  • 1986-12. A unified approach to visibility representations of planar graphs in DISCRETE & COMPUTATIONAL GEOMETRY
  • Identifiers

    URI

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

    DOI

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

    DIMENSIONS

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


    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": "French National Centre for Scientific Research", 
              "id": "https://www.grid.ac/institutes/grid.4444.0", 
              "name": [
                "CNRS, Paris, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "De Fraysseix", 
            "givenName": "H.", 
            "id": "sg:person.011477335121.34", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011477335121.34"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Courant Institute of Mathematical Sciences", 
              "id": "https://www.grid.ac/institutes/grid.482020.c", 
              "name": [
                "Mathematical Institute of the Hungarian Academy of Sciences, Hungary", 
                "Courant Institute, NYU, New York, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Pach", 
            "givenName": "J.", 
            "id": "sg:person.016440471013.73", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016440471013.73"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Courant Institute of Mathematical Sciences", 
              "id": "https://www.grid.ac/institutes/grid.482020.c", 
              "name": [
                "Courant Institute, NYU, New York, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Pollack", 
            "givenName": "R.", 
            "id": "sg:person.01332004574.46", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01332004574.46"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf02187706", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008881195", 
              "https://doi.org/10.1007/bf02187706"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187706", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008881195", 
              "https://doi.org/10.1007/bf02187706"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187706", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008881195", 
              "https://doi.org/10.1007/bf02187706"
            ], 
            "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": "sg:pub.10.1007/bf02187705", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027312329", 
              "https://doi.org/10.1007/bf02187705"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187705", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027312329", 
              "https://doi.org/10.1007/bf02187705"
            ], 
            "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.1109/tc.1981.6312176", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061532644"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1990-03", 
        "datePublishedReg": "1990-03-01", 
        "description": "Answering a question of Rosenstiehl and Tarjan, we show that every plane graph withn vertices has a F\u00e1ry embedding (i.e., straight-line embedding) on the 2n\u22124 byn\u22122 grid and provide anO(n) space,O(n logn) time algorithm to effect this embedding. The grid size is asymptotically optimal and it had been previously unknown whether one can always find a polynomial sized grid to support such an embedding. On the other hand we show that any setF, which can support a F\u00e1ry embedding of every planar graph of sizen, has cardinality at leastn+(1\u2212o(1))\u221an which settles a problem of Mohar.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/bf02122694", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136493", 
            "issn": [
              "0209-9683", 
              "1439-6912"
            ], 
            "name": "Combinatorica", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "10"
          }
        ], 
        "name": "How to draw a planar graph on a grid", 
        "pagination": "41-51", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "1c3b213c7d077ca8eec0c32a914ca3a306ad16c843972808a0e84b4e5d0d567d"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf02122694"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1005926153"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf02122694", 
          "https://app.dimensions.ai/details/publication/pub.1005926153"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T12:55", 
        "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/0000000364_0000000364/records_72869_00000000.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/BF02122694"
      }
    ]
     

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

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

    Turtle is a human-readable linked data format.

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

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

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


     

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

    102 TRIPLES      21 PREDICATES      34 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf02122694 schema:about anzsrc-for:08
    2 anzsrc-for:0806
    3 schema:author N09bc15e27b18474d8f27c40e6bd4a43c
    4 schema:citation sg:pub.10.1007/bf02187705
    5 sg:pub.10.1007/bf02187706
    6 https://doi.org/10.1016/0012-365x(83)90128-0
    7 https://doi.org/10.1109/tc.1981.6312176
    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.1145/321850.321852
    11 schema:datePublished 1990-03
    12 schema:datePublishedReg 1990-03-01
    13 schema:description Answering a question of Rosenstiehl and Tarjan, we show that every plane graph withn vertices has a Fáry embedding (i.e., straight-line embedding) on the 2n−4 byn−2 grid and provide anO(n) space,O(n logn) time algorithm to effect this embedding. The grid size is asymptotically optimal and it had been previously unknown whether one can always find a polynomial sized grid to support such an embedding. On the other hand we show that any setF, which can support a Fáry embedding of every planar graph of sizen, has cardinality at leastn+(1−o(1))√n which settles a problem of Mohar.
    14 schema:genre research_article
    15 schema:inLanguage en
    16 schema:isAccessibleForFree false
    17 schema:isPartOf N2198b8dd270f4fc4b25720128c4c91aa
    18 N7259fde09aae45f39423757c6dd14a9d
    19 sg:journal.1136493
    20 schema:name How to draw a planar graph on a grid
    21 schema:pagination 41-51
    22 schema:productId N1b0248feb9e5461d8ce50b8b14fe2bef
    23 N4f10b835d532409ea1bb254e6d0de0d2
    24 N9b92c0c111af438eb5d0a6e0ddd67700
    25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005926153
    26 https://doi.org/10.1007/bf02122694
    27 schema:sdDatePublished 2019-04-11T12:55
    28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    29 schema:sdPublisher N26e06692fe7f487ebdcea300fab689a0
    30 schema:url http://link.springer.com/10.1007/BF02122694
    31 sgo:license sg:explorer/license/
    32 sgo:sdDataset articles
    33 rdf:type schema:ScholarlyArticle
    34 N09bc15e27b18474d8f27c40e6bd4a43c rdf:first sg:person.011477335121.34
    35 rdf:rest Na419ccc0c30d41cba077d6b2a7b15c88
    36 N1b0248feb9e5461d8ce50b8b14fe2bef schema:name dimensions_id
    37 schema:value pub.1005926153
    38 rdf:type schema:PropertyValue
    39 N2198b8dd270f4fc4b25720128c4c91aa schema:issueNumber 1
    40 rdf:type schema:PublicationIssue
    41 N26e06692fe7f487ebdcea300fab689a0 schema:name Springer Nature - SN SciGraph project
    42 rdf:type schema:Organization
    43 N4f10b835d532409ea1bb254e6d0de0d2 schema:name readcube_id
    44 schema:value 1c3b213c7d077ca8eec0c32a914ca3a306ad16c843972808a0e84b4e5d0d567d
    45 rdf:type schema:PropertyValue
    46 N7259fde09aae45f39423757c6dd14a9d schema:volumeNumber 10
    47 rdf:type schema:PublicationVolume
    48 N9b92c0c111af438eb5d0a6e0ddd67700 schema:name doi
    49 schema:value 10.1007/bf02122694
    50 rdf:type schema:PropertyValue
    51 Na419ccc0c30d41cba077d6b2a7b15c88 rdf:first sg:person.016440471013.73
    52 rdf:rest Nf830fb76b88c44c6827be7534cbbe31a
    53 Nf830fb76b88c44c6827be7534cbbe31a rdf:first sg:person.01332004574.46
    54 rdf:rest rdf:nil
    55 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    56 schema:name Information and Computing Sciences
    57 rdf:type schema:DefinedTerm
    58 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
    59 schema:name Information Systems
    60 rdf:type schema:DefinedTerm
    61 sg:journal.1136493 schema:issn 0209-9683
    62 1439-6912
    63 schema:name Combinatorica
    64 rdf:type schema:Periodical
    65 sg:person.011477335121.34 schema:affiliation https://www.grid.ac/institutes/grid.4444.0
    66 schema:familyName De Fraysseix
    67 schema:givenName H.
    68 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011477335121.34
    69 rdf:type schema:Person
    70 sg:person.01332004574.46 schema:affiliation https://www.grid.ac/institutes/grid.482020.c
    71 schema:familyName Pollack
    72 schema:givenName R.
    73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01332004574.46
    74 rdf:type schema:Person
    75 sg:person.016440471013.73 schema:affiliation https://www.grid.ac/institutes/grid.482020.c
    76 schema:familyName Pach
    77 schema:givenName J.
    78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016440471013.73
    79 rdf:type schema:Person
    80 sg:pub.10.1007/bf02187705 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027312329
    81 https://doi.org/10.1007/bf02187705
    82 rdf:type schema:CreativeWork
    83 sg:pub.10.1007/bf02187706 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008881195
    84 https://doi.org/10.1007/bf02187706
    85 rdf:type schema:CreativeWork
    86 https://doi.org/10.1016/0012-365x(83)90128-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041600793
    87 rdf:type schema:CreativeWork
    88 https://doi.org/10.1109/tc.1981.6312176 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061532644
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1111/j.1749-6632.1989.tb22470.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1023776586
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1112/plms/s3-13.1.743 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040536272
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1145/321850.321852 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023277958
    95 rdf:type schema:CreativeWork
    96 https://www.grid.ac/institutes/grid.4444.0 schema:alternateName French National Centre for Scientific Research
    97 schema:name CNRS, Paris, France
    98 rdf:type schema:Organization
    99 https://www.grid.ac/institutes/grid.482020.c schema:alternateName Courant Institute of Mathematical Sciences
    100 schema:name Courant Institute, NYU, New York, USA
    101 Mathematical Institute of the Hungarian Academy of Sciences, Hungary
    102 rdf:type schema:Organization
     




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


    ...