Drawing planar graphs using the canonical ordering View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1996-07

AUTHORS

G. Kant

ABSTRACT

We introduce a new method to optimize the required area, minimum angle, and number of bends of planar graph drawings on a grid. The main tool is a new type of ordering on the vertices and faces of triconnected planar graphs. Using this method linear-time-and-space algorithms can be designed for many graph-drawing problems. Our main results are as follows:Every triconnected planar graphG admits a planar convex grid drawing with straight lines on a (2n−4)×(n−2) grid, wheren is the number of vertices.Every triconnected planar graph with maximum degree 4 admits a planar orthogonal grid drawing on ann×n grid with at most [3n/2]+4 bends, and ifn>6, then every edge has at most two bends.Every planar graph with maximum degree 3 admits a planar orthogonal grid drawing with at most [n/2]+1 bends on an [n/2]×[n/2] grid.Every triconnected planar graphG admits a planar polyline grid drawing on a (2n−6)×(3n−9) grid with minimum angle larger than 2/d radians and at most 5n−15 bends, withd the maximum degree. Every triconnected planar graphG admits a planar convex grid drawing with straight lines on a (2n−4)×(n−2) grid, wheren is the number of vertices. Every triconnected planar graph with maximum degree 4 admits a planar orthogonal grid drawing on ann×n grid with at most [3n/2]+4 bends, and ifn>6, then every edge has at most two bends. Every planar graph with maximum degree 3 admits a planar orthogonal grid drawing with at most [n/2]+1 bends on an [n/2]×[n/2] grid. Every triconnected planar graphG admits a planar polyline grid drawing on a (2n−6)×(3n−9) grid with minimum angle larger than 2/d radians and at most 5n−15 bends, withd the maximum degree. These results give in some cases considerable improvements over previous results, and give new bounds in other cases. Several other results, e.g., concerning visibility representations, are included. More... »

PAGES

4-32

References to SciGraph publications

  • 1995. On the computational complexity of upward and rectilinear planarity testing in GRAPH DRAWING
  • 1994. Two algorithms for finding rectangular duals of planar graphs in GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
  • 1988-11. A linear algorithm to find a rectangular dual of a planar triangulated graph in ALGORITHMICA
  • 1994. Planar drawings and angular resolution: Algorithms and bounds in ALGORITHMS — ESA '94
  • 1994. A more compact visibility representation in GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
  • 1993. Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs (extended abstract) in ALGORITHMS AND DATA STRUCTURES
  • 1993. Parallel construction of canonical ordering and convex drawing of triconnected planar graphs in ALGORITHMS AND COMPUTATION
  • 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
  • 1992-04. Area requirement and symmetry display of planar upward drawings in DISCRETE & COMPUTATIONAL GEOMETRY
  • 1990-03. How to draw a planar graph on a grid in COMBINATORICA
  • 1993. Hexagonal grid drawings in GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
  • 1992-04. Theoretical results on at most 1-bend embeddability of graphs in ACTA MATHEMATICAE APPLICATAE SINICA, ENGLISH SERIES
  • 1985-06. Drawing plane graphs nicely in ACTA INFORMATICA
  • Identifiers

    URI

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

    DOI

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

    DIMENSIONS

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


    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": "Utrecht University", 
              "id": "https://www.grid.ac/institutes/grid.5477.1", 
              "name": [
                "Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508, TB Utrecht, The Netherlands"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kant", 
            "givenName": "G.", 
            "id": "sg:person.013743554756.94", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013743554756.94"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf01762117", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003139574", 
              "https://doi.org/10.1007/bf01762117"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01762117", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003139574", 
              "https://doi.org/10.1007/bf01762117"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-57155-8_244", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005416239", 
              "https://doi.org/10.1007/3-540-57155-8_244"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02122694", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005926153", 
              "https://doi.org/10.1007/bf02122694"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02122694", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005926153", 
              "https://doi.org/10.1007/bf02122694"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02122694", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005926153", 
              "https://doi.org/10.1007/bf02122694"
            ], 
            "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": "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/3-540-57899-4_70", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012839777", 
              "https://doi.org/10.1007/3-540-57899-4_70"
            ], 
            "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": "sg:pub.10.1007/3-540-57899-4_69", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018910920", 
              "https://doi.org/10.1007/3-540-57899-4_69"
            ], 
            "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.1002/net.3230140202", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023775252"
            ], 
            "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.1016/s0022-0000(76)80045-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030334487"
            ], 
            "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": "sg:pub.10.1007/3-540-58950-3_384", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031098794", 
              "https://doi.org/10.1007/3-540-58950-3_384"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0049393", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031647520", 
              "https://doi.org/10.1007/bfb0049393"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/s0002-9939-1951-0041425-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032762886"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02006154", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035226061", 
              "https://doi.org/10.1007/bf02006154"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02006154", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035226061", 
              "https://doi.org/10.1007/bf02006154"
            ], 
            "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": "sg:pub.10.1007/3-540-57568-5_261", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039080031", 
              "https://doi.org/10.1007/3-540-57568-5_261"
            ], 
            "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.1145/142675.142728", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041197738"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-56402-0_53", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043848821", 
              "https://doi.org/10.1007/3-540-56402-0_53"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(92)90349-k", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044028443"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0925-7721(94)00014-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049116874"
            ], 
            "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.1016/0020-0190(91)90059-q", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052090013"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00264230", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052102689", 
              "https://doi.org/10.1007/bf00264230"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00264230", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052102689", 
              "https://doi.org/10.1007/bf00264230"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187850", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053554536", 
              "https://doi.org/10.1007/bf02187850"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187850", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053554536", 
              "https://doi.org/10.1007/bf02187850"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/31.1746", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061152809"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/31.34669", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061153032"
            ], 
            "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/0216030", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841976"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0222063", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062842466"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0222072", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062842475"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0895480193242931", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062882900"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1142/s0218195997000144", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062960880"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1989.63515", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086220172"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1996-07", 
        "datePublishedReg": "1996-07-01", 
        "description": "We introduce a new method to optimize the required area, minimum angle, and number of bends of planar graph drawings on a grid. The main tool is a new type of ordering on the vertices and faces of triconnected planar graphs. Using this method linear-time-and-space algorithms can be designed for many graph-drawing problems. Our main results are as follows:Every triconnected planar graphG admits a planar convex grid drawing with straight lines on a (2n\u22124)\u00d7(n\u22122) grid, wheren is the number of vertices.Every triconnected planar graph with maximum degree 4 admits a planar orthogonal grid drawing on ann\u00d7n grid with at most [3n/2]+4 bends, and ifn>6, then every edge has at most two bends.Every planar graph with maximum degree 3 admits a planar orthogonal grid drawing with at most [n/2]+1 bends on an [n/2]\u00d7[n/2] grid.Every triconnected planar graphG admits a planar polyline grid drawing on a (2n\u22126)\u00d7(3n\u22129) grid with minimum angle larger than 2/d radians and at most 5n\u221215 bends, withd the maximum degree. Every triconnected planar graphG admits a planar convex grid drawing with straight lines on a (2n\u22124)\u00d7(n\u22122) grid, wheren is the number of vertices. Every triconnected planar graph with maximum degree 4 admits a planar orthogonal grid drawing on ann\u00d7n grid with at most [3n/2]+4 bends, and ifn>6, then every edge has at most two bends. Every planar graph with maximum degree 3 admits a planar orthogonal grid drawing with at most [n/2]+1 bends on an [n/2]\u00d7[n/2] grid. Every triconnected planar graphG admits a planar polyline grid drawing on a (2n\u22126)\u00d7(3n\u22129) grid with minimum angle larger than 2/d radians and at most 5n\u221215 bends, withd the maximum degree. These results give in some cases considerable improvements over previous results, and give new bounds in other cases. Several other results, e.g., concerning visibility representations, are included.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/bf02086606", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "16"
          }
        ], 
        "name": "Drawing planar graphs using the canonical ordering", 
        "pagination": "4-32", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "736dc031e71a8a2d543144df1e046b14b0b28c422ab2028d266cd16efc2ef6df"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf02086606"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1024228802"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf02086606", 
          "https://app.dimensions.ai/details/publication/pub.1024228802"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T11:56", 
        "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/0000000359_0000000359/records_29215_00000001.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/BF02086606"
      }
    ]
     

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

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

    Turtle is a human-readable linked data format.

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

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

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


     

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

    183 TRIPLES      21 PREDICATES      63 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf02086606 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N788a15b032374375a094bdd42eab265e
    4 schema:citation sg:pub.10.1007/3-540-56402-0_53
    5 sg:pub.10.1007/3-540-57155-8_244
    6 sg:pub.10.1007/3-540-57568-5_261
    7 sg:pub.10.1007/3-540-57899-4_69
    8 sg:pub.10.1007/3-540-57899-4_70
    9 sg:pub.10.1007/3-540-58950-3_384
    10 sg:pub.10.1007/bf00264230
    11 sg:pub.10.1007/bf01762117
    12 sg:pub.10.1007/bf02006154
    13 sg:pub.10.1007/bf02122694
    14 sg:pub.10.1007/bf02187705
    15 sg:pub.10.1007/bf02187706
    16 sg:pub.10.1007/bf02187850
    17 sg:pub.10.1007/bfb0049393
    18 https://doi.org/10.1002/net.3230140202
    19 https://doi.org/10.1016/0020-0190(91)90059-q
    20 https://doi.org/10.1016/0022-0000(85)90004-2
    21 https://doi.org/10.1016/0095-8956(80)90083-0
    22 https://doi.org/10.1016/0304-3975(76)90086-4
    23 https://doi.org/10.1016/0304-3975(92)90349-k
    24 https://doi.org/10.1016/0925-7721(94)00014-x
    25 https://doi.org/10.1016/s0022-0000(76)80045-1
    26 https://doi.org/10.1090/s0002-9939-1951-0041425-5
    27 https://doi.org/10.1109/31.1746
    28 https://doi.org/10.1109/31.34669
    29 https://doi.org/10.1109/sfcs.1989.63515
    30 https://doi.org/10.1112/plms/s3-10.1.304
    31 https://doi.org/10.1112/plms/s3-13.1.743
    32 https://doi.org/10.1137/0202012
    33 https://doi.org/10.1137/0216030
    34 https://doi.org/10.1137/0222063
    35 https://doi.org/10.1137/0222072
    36 https://doi.org/10.1137/s0895480193242931
    37 https://doi.org/10.1142/s0218195997000144
    38 https://doi.org/10.1145/142675.142728
    39 https://doi.org/10.1145/321850.321852
    40 schema:datePublished 1996-07
    41 schema:datePublishedReg 1996-07-01
    42 schema:description We introduce a new method to optimize the required area, minimum angle, and number of bends of planar graph drawings on a grid. The main tool is a new type of ordering on the vertices and faces of triconnected planar graphs. Using this method linear-time-and-space algorithms can be designed for many graph-drawing problems. Our main results are as follows:Every triconnected planar graphG admits a planar convex grid drawing with straight lines on a (2n−4)×(n−2) grid, wheren is the number of vertices.Every triconnected planar graph with maximum degree 4 admits a planar orthogonal grid drawing on ann×n grid with at most [3n/2]+4 bends, and ifn>6, then every edge has at most two bends.Every planar graph with maximum degree 3 admits a planar orthogonal grid drawing with at most [n/2]+1 bends on an [n/2]×[n/2] grid.Every triconnected planar graphG admits a planar polyline grid drawing on a (2n−6)×(3n−9) grid with minimum angle larger than 2/d radians and at most 5n−15 bends, withd the maximum degree. Every triconnected planar graphG admits a planar convex grid drawing with straight lines on a (2n−4)×(n−2) grid, wheren is the number of vertices. Every triconnected planar graph with maximum degree 4 admits a planar orthogonal grid drawing on ann×n grid with at most [3n/2]+4 bends, and ifn>6, then every edge has at most two bends. Every planar graph with maximum degree 3 admits a planar orthogonal grid drawing with at most [n/2]+1 bends on an [n/2]×[n/2] grid. Every triconnected planar graphG admits a planar polyline grid drawing on a (2n−6)×(3n−9) grid with minimum angle larger than 2/d radians and at most 5n−15 bends, withd the maximum degree. These results give in some cases considerable improvements over previous results, and give new bounds in other cases. Several other results, e.g., concerning visibility representations, are included.
    43 schema:genre research_article
    44 schema:inLanguage en
    45 schema:isAccessibleForFree true
    46 schema:isPartOf N881bb0dce2c244d8beacc7f8a0f83434
    47 Nac76e4295a7b4640b0d2d0cde546080b
    48 sg:journal.1047644
    49 schema:name Drawing planar graphs using the canonical ordering
    50 schema:pagination 4-32
    51 schema:productId N06370f4ce469446b9f6eb8a23da15e18
    52 N12be171413ab4f62ba977d3810e5f779
    53 Nafdde474d2a340fcb79fd9646e4999c3
    54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024228802
    55 https://doi.org/10.1007/bf02086606
    56 schema:sdDatePublished 2019-04-11T11:56
    57 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    58 schema:sdPublisher Nc203fc2408e1473a924752e637f71cba
    59 schema:url http://link.springer.com/10.1007/BF02086606
    60 sgo:license sg:explorer/license/
    61 sgo:sdDataset articles
    62 rdf:type schema:ScholarlyArticle
    63 N06370f4ce469446b9f6eb8a23da15e18 schema:name dimensions_id
    64 schema:value pub.1024228802
    65 rdf:type schema:PropertyValue
    66 N12be171413ab4f62ba977d3810e5f779 schema:name readcube_id
    67 schema:value 736dc031e71a8a2d543144df1e046b14b0b28c422ab2028d266cd16efc2ef6df
    68 rdf:type schema:PropertyValue
    69 N788a15b032374375a094bdd42eab265e rdf:first sg:person.013743554756.94
    70 rdf:rest rdf:nil
    71 N881bb0dce2c244d8beacc7f8a0f83434 schema:issueNumber 1
    72 rdf:type schema:PublicationIssue
    73 Nac76e4295a7b4640b0d2d0cde546080b schema:volumeNumber 16
    74 rdf:type schema:PublicationVolume
    75 Nafdde474d2a340fcb79fd9646e4999c3 schema:name doi
    76 schema:value 10.1007/bf02086606
    77 rdf:type schema:PropertyValue
    78 Nc203fc2408e1473a924752e637f71cba schema:name Springer Nature - SN SciGraph project
    79 rdf:type schema:Organization
    80 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    81 schema:name Information and Computing Sciences
    82 rdf:type schema:DefinedTerm
    83 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    84 schema:name Computation Theory and Mathematics
    85 rdf:type schema:DefinedTerm
    86 sg:journal.1047644 schema:issn 0178-4617
    87 1432-0541
    88 schema:name Algorithmica
    89 rdf:type schema:Periodical
    90 sg:person.013743554756.94 schema:affiliation https://www.grid.ac/institutes/grid.5477.1
    91 schema:familyName Kant
    92 schema:givenName G.
    93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013743554756.94
    94 rdf:type schema:Person
    95 sg:pub.10.1007/3-540-56402-0_53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043848821
    96 https://doi.org/10.1007/3-540-56402-0_53
    97 rdf:type schema:CreativeWork
    98 sg:pub.10.1007/3-540-57155-8_244 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005416239
    99 https://doi.org/10.1007/3-540-57155-8_244
    100 rdf:type schema:CreativeWork
    101 sg:pub.10.1007/3-540-57568-5_261 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039080031
    102 https://doi.org/10.1007/3-540-57568-5_261
    103 rdf:type schema:CreativeWork
    104 sg:pub.10.1007/3-540-57899-4_69 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018910920
    105 https://doi.org/10.1007/3-540-57899-4_69
    106 rdf:type schema:CreativeWork
    107 sg:pub.10.1007/3-540-57899-4_70 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012839777
    108 https://doi.org/10.1007/3-540-57899-4_70
    109 rdf:type schema:CreativeWork
    110 sg:pub.10.1007/3-540-58950-3_384 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031098794
    111 https://doi.org/10.1007/3-540-58950-3_384
    112 rdf:type schema:CreativeWork
    113 sg:pub.10.1007/bf00264230 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052102689
    114 https://doi.org/10.1007/bf00264230
    115 rdf:type schema:CreativeWork
    116 sg:pub.10.1007/bf01762117 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003139574
    117 https://doi.org/10.1007/bf01762117
    118 rdf:type schema:CreativeWork
    119 sg:pub.10.1007/bf02006154 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035226061
    120 https://doi.org/10.1007/bf02006154
    121 rdf:type schema:CreativeWork
    122 sg:pub.10.1007/bf02122694 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005926153
    123 https://doi.org/10.1007/bf02122694
    124 rdf:type schema:CreativeWork
    125 sg:pub.10.1007/bf02187705 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027312329
    126 https://doi.org/10.1007/bf02187705
    127 rdf:type schema:CreativeWork
    128 sg:pub.10.1007/bf02187706 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008881195
    129 https://doi.org/10.1007/bf02187706
    130 rdf:type schema:CreativeWork
    131 sg:pub.10.1007/bf02187850 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053554536
    132 https://doi.org/10.1007/bf02187850
    133 rdf:type schema:CreativeWork
    134 sg:pub.10.1007/bfb0049393 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031647520
    135 https://doi.org/10.1007/bfb0049393
    136 rdf:type schema:CreativeWork
    137 https://doi.org/10.1002/net.3230140202 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023775252
    138 rdf:type schema:CreativeWork
    139 https://doi.org/10.1016/0020-0190(91)90059-q schema:sameAs https://app.dimensions.ai/details/publication/pub.1052090013
    140 rdf:type schema:CreativeWork
    141 https://doi.org/10.1016/0022-0000(85)90004-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030929286
    142 rdf:type schema:CreativeWork
    143 https://doi.org/10.1016/0095-8956(80)90083-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016550143
    144 rdf:type schema:CreativeWork
    145 https://doi.org/10.1016/0304-3975(76)90086-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035496339
    146 rdf:type schema:CreativeWork
    147 https://doi.org/10.1016/0304-3975(92)90349-k schema:sameAs https://app.dimensions.ai/details/publication/pub.1044028443
    148 rdf:type schema:CreativeWork
    149 https://doi.org/10.1016/0925-7721(94)00014-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1049116874
    150 rdf:type schema:CreativeWork
    151 https://doi.org/10.1016/s0022-0000(76)80045-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030334487
    152 rdf:type schema:CreativeWork
    153 https://doi.org/10.1090/s0002-9939-1951-0041425-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032762886
    154 rdf:type schema:CreativeWork
    155 https://doi.org/10.1109/31.1746 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061152809
    156 rdf:type schema:CreativeWork
    157 https://doi.org/10.1109/31.34669 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061153032
    158 rdf:type schema:CreativeWork
    159 https://doi.org/10.1109/sfcs.1989.63515 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086220172
    160 rdf:type schema:CreativeWork
    161 https://doi.org/10.1112/plms/s3-10.1.304 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051445647
    162 rdf:type schema:CreativeWork
    163 https://doi.org/10.1112/plms/s3-13.1.743 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040536272
    164 rdf:type schema:CreativeWork
    165 https://doi.org/10.1137/0202012 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841200
    166 rdf:type schema:CreativeWork
    167 https://doi.org/10.1137/0216030 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841976
    168 rdf:type schema:CreativeWork
    169 https://doi.org/10.1137/0222063 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842466
    170 rdf:type schema:CreativeWork
    171 https://doi.org/10.1137/0222072 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842475
    172 rdf:type schema:CreativeWork
    173 https://doi.org/10.1137/s0895480193242931 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062882900
    174 rdf:type schema:CreativeWork
    175 https://doi.org/10.1142/s0218195997000144 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062960880
    176 rdf:type schema:CreativeWork
    177 https://doi.org/10.1145/142675.142728 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041197738
    178 rdf:type schema:CreativeWork
    179 https://doi.org/10.1145/321850.321852 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023277958
    180 rdf:type schema:CreativeWork
    181 https://www.grid.ac/institutes/grid.5477.1 schema:alternateName Utrecht University
    182 schema:name Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508, TB Utrecht, The Netherlands
    183 rdf:type schema:Organization
     




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


    ...