Two algorithms for three dimensional orthogonal graph drawing View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1997

AUTHORS

Peter Eades , Antonios Symvonis , Sue Whitesides

ABSTRACT

We use basic results from graph theory to design two algorithms for constructing 3-dimensional, intersection-free orthogonal grid drawings of n vertex graphs of maximum degree 6. Our first algorithm gives drawings bounded by an O(√n× O(√n) × O(√n) box; each edge route contains at most 7 bends. The best previous result generated edge routes containing up to 16 bends per route. Our second algorithm gives drawings having at most 3 bends per edge route. The drawings lie in an O(n)×O(n) × O(n) bounding box. Together, the two algorithms initiate the study of bend/bounding box trade-off issues for 3-dimensional grid drawings. More... »

PAGES

139-154

References to SciGraph publications

  • 1983-12. Optimal three-dimensional VLSI layouts in MATHEMATICAL SYSTEMS THEORY
  • Book

    TITLE

    Graph Drawing

    ISBN

    978-3-540-62495-0
    978-3-540-68048-2

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-62495-3_44

    DOI

    http://dx.doi.org/10.1007/3-540-62495-3_44

    DIMENSIONS

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


    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": {
              "alternateName": "University of Newcastle Australia", 
              "id": "https://www.grid.ac/institutes/grid.266842.c", 
              "name": [
                "Dept. of Computer Science, University of Newcastle, 2308, N.S.W., Australia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Eades", 
            "givenName": "Peter", 
            "id": "sg:person.01314347503.31", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01314347503.31"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Sydney", 
              "id": "https://www.grid.ac/institutes/grid.1013.3", 
              "name": [
                "Basser Dept. of Computer Science, University of Sydney, 2006, N.S.W., Australia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Symvonis", 
            "givenName": "Antonios", 
            "id": "sg:person.015542102631.22", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015542102631.22"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "McGill University", 
              "id": "https://www.grid.ac/institutes/grid.14709.3b", 
              "name": [
                "School of Computer Science, McGill University, H3A 2A7\u00a0Montreal, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Whitesides", 
            "givenName": "Sue", 
            "id": "sg:person.07560613205.66", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07560613205.66"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf01744565", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007486192", 
              "https://doi.org/10.1007/bf01744565"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01744565", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007486192", 
              "https://doi.org/10.1007/bf01744565"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0166-218x(94)00020-e", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045941031"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(87)90173-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048894850"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(87)90173-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048894850"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2402.322384", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051032720"
            ], 
            "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/0202019", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841207"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0216030", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841976"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1997", 
        "datePublishedReg": "1997-01-01", 
        "description": "We use basic results from graph theory to design two algorithms for constructing 3-dimensional, intersection-free orthogonal grid drawings of n vertex graphs of maximum degree 6. Our first algorithm gives drawings bounded by an O(\u221an\u00d7 O(\u221an) \u00d7 O(\u221an) box; each edge route contains at most 7 bends. The best previous result generated edge routes containing up to 16 bends per route. Our second algorithm gives drawings having at most 3 bends per edge route. The drawings lie in an O(n)\u00d7O(n) \u00d7 O(n) bounding box. Together, the two algorithms initiate the study of bend/bounding box trade-off issues for 3-dimensional grid drawings.", 
        "editor": [
          {
            "familyName": "North", 
            "givenName": "Stephen", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-62495-3_44", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-62495-0", 
            "978-3-540-68048-2"
          ], 
          "name": "Graph Drawing", 
          "type": "Book"
        }, 
        "name": "Two algorithms for three dimensional orthogonal graph drawing", 
        "pagination": "139-154", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-62495-3_44"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "01566caf2b2c282eebc2c13bf1a69228d473e1bb49773f677dd9ada15352ab5b"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1000281398"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-62495-3_44", 
          "https://app.dimensions.ai/details/publication/pub.1000281398"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T20:59", 
        "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/0000000001_0000000264/records_8690_00000243.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/3-540-62495-3_44"
      }
    ]
     

    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/3-540-62495-3_44'

    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/3-540-62495-3_44'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-62495-3_44'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-62495-3_44'


     

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

    107 TRIPLES      23 PREDICATES      34 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-62495-3_44 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N8201e6a024214faea22df3c7bc50e034
    4 schema:citation sg:pub.10.1007/bf01744565
    5 https://doi.org/10.1016/0020-0190(87)90173-6
    6 https://doi.org/10.1016/0166-218x(94)00020-e
    7 https://doi.org/10.1109/31.34669
    8 https://doi.org/10.1137/0202019
    9 https://doi.org/10.1137/0216030
    10 https://doi.org/10.1145/2402.322384
    11 schema:datePublished 1997
    12 schema:datePublishedReg 1997-01-01
    13 schema:description We use basic results from graph theory to design two algorithms for constructing 3-dimensional, intersection-free orthogonal grid drawings of n vertex graphs of maximum degree 6. Our first algorithm gives drawings bounded by an O(√n× O(√n) × O(√n) box; each edge route contains at most 7 bends. The best previous result generated edge routes containing up to 16 bends per route. Our second algorithm gives drawings having at most 3 bends per edge route. The drawings lie in an O(n)×O(n) × O(n) bounding box. Together, the two algorithms initiate the study of bend/bounding box trade-off issues for 3-dimensional grid drawings.
    14 schema:editor N67419c61b7fd4689b3f2736a86764e4f
    15 schema:genre chapter
    16 schema:inLanguage en
    17 schema:isAccessibleForFree true
    18 schema:isPartOf N03d1279c4bd04e42966e5e1d7fc4692b
    19 schema:name Two algorithms for three dimensional orthogonal graph drawing
    20 schema:pagination 139-154
    21 schema:productId N43ba3b22062d4a189c4f301d95e14352
    22 N5c3b5f325e6440fda2539835f54262c5
    23 N629dd50cfcd74912856239307de14cae
    24 schema:publisher N0d19e0db1a1649768c9704de501531b9
    25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000281398
    26 https://doi.org/10.1007/3-540-62495-3_44
    27 schema:sdDatePublished 2019-04-15T20:59
    28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    29 schema:sdPublisher N2b2b727c5c2c42b4887355220ff8b470
    30 schema:url http://link.springer.com/10.1007/3-540-62495-3_44
    31 sgo:license sg:explorer/license/
    32 sgo:sdDataset chapters
    33 rdf:type schema:Chapter
    34 N03d1279c4bd04e42966e5e1d7fc4692b schema:isbn 978-3-540-62495-0
    35 978-3-540-68048-2
    36 schema:name Graph Drawing
    37 rdf:type schema:Book
    38 N0d19e0db1a1649768c9704de501531b9 schema:location Berlin, Heidelberg
    39 schema:name Springer Berlin Heidelberg
    40 rdf:type schema:Organisation
    41 N2b2b727c5c2c42b4887355220ff8b470 schema:name Springer Nature - SN SciGraph project
    42 rdf:type schema:Organization
    43 N372e376474b04a2a9df9bc5f34a5389e rdf:first sg:person.07560613205.66
    44 rdf:rest rdf:nil
    45 N43ba3b22062d4a189c4f301d95e14352 schema:name readcube_id
    46 schema:value 01566caf2b2c282eebc2c13bf1a69228d473e1bb49773f677dd9ada15352ab5b
    47 rdf:type schema:PropertyValue
    48 N5c3b5f325e6440fda2539835f54262c5 schema:name dimensions_id
    49 schema:value pub.1000281398
    50 rdf:type schema:PropertyValue
    51 N629dd50cfcd74912856239307de14cae schema:name doi
    52 schema:value 10.1007/3-540-62495-3_44
    53 rdf:type schema:PropertyValue
    54 N67419c61b7fd4689b3f2736a86764e4f rdf:first N7bc17363943c4d65adf435ac8f639fc0
    55 rdf:rest rdf:nil
    56 N7bc17363943c4d65adf435ac8f639fc0 schema:familyName North
    57 schema:givenName Stephen
    58 rdf:type schema:Person
    59 N8201e6a024214faea22df3c7bc50e034 rdf:first sg:person.01314347503.31
    60 rdf:rest Ndb30d2bcc0024ecbbad1e44621e6876f
    61 Ndb30d2bcc0024ecbbad1e44621e6876f rdf:first sg:person.015542102631.22
    62 rdf:rest N372e376474b04a2a9df9bc5f34a5389e
    63 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    64 schema:name Mathematical Sciences
    65 rdf:type schema:DefinedTerm
    66 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    67 schema:name Pure Mathematics
    68 rdf:type schema:DefinedTerm
    69 sg:person.01314347503.31 schema:affiliation https://www.grid.ac/institutes/grid.266842.c
    70 schema:familyName Eades
    71 schema:givenName Peter
    72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01314347503.31
    73 rdf:type schema:Person
    74 sg:person.015542102631.22 schema:affiliation https://www.grid.ac/institutes/grid.1013.3
    75 schema:familyName Symvonis
    76 schema:givenName Antonios
    77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015542102631.22
    78 rdf:type schema:Person
    79 sg:person.07560613205.66 schema:affiliation https://www.grid.ac/institutes/grid.14709.3b
    80 schema:familyName Whitesides
    81 schema:givenName Sue
    82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07560613205.66
    83 rdf:type schema:Person
    84 sg:pub.10.1007/bf01744565 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007486192
    85 https://doi.org/10.1007/bf01744565
    86 rdf:type schema:CreativeWork
    87 https://doi.org/10.1016/0020-0190(87)90173-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048894850
    88 rdf:type schema:CreativeWork
    89 https://doi.org/10.1016/0166-218x(94)00020-e schema:sameAs https://app.dimensions.ai/details/publication/pub.1045941031
    90 rdf:type schema:CreativeWork
    91 https://doi.org/10.1109/31.34669 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061153032
    92 rdf:type schema:CreativeWork
    93 https://doi.org/10.1137/0202019 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841207
    94 rdf:type schema:CreativeWork
    95 https://doi.org/10.1137/0216030 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841976
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1145/2402.322384 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051032720
    98 rdf:type schema:CreativeWork
    99 https://www.grid.ac/institutes/grid.1013.3 schema:alternateName University of Sydney
    100 schema:name Basser Dept. of Computer Science, University of Sydney, 2006, N.S.W., Australia
    101 rdf:type schema:Organization
    102 https://www.grid.ac/institutes/grid.14709.3b schema:alternateName McGill University
    103 schema:name School of Computer Science, McGill University, H3A 2A7 Montreal, Canada
    104 rdf:type schema:Organization
    105 https://www.grid.ac/institutes/grid.266842.c schema:alternateName University of Newcastle Australia
    106 schema:name Dept. of Computer Science, University of Newcastle, 2308, N.S.W., Australia
    107 rdf:type schema:Organization
     




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


    ...