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 Nb0d7207353c6402bb5ccd94c41247ed4
    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 Ne81183bf65c1445ab1d3036a4b67d6a9
    15 schema:genre chapter
    16 schema:inLanguage en
    17 schema:isAccessibleForFree true
    18 schema:isPartOf N9f7afdf2e6c74b4595ac088c7f7cadad
    19 schema:name Two algorithms for three dimensional orthogonal graph drawing
    20 schema:pagination 139-154
    21 schema:productId N219eb66c1ec54988a1e38272e5d5e9a1
    22 N35dbc9e6f9cd498a93a4a1b73856e839
    23 Nfcbfadec2c454a8580e7f61e98524ad4
    24 schema:publisher N50d2b3e241524539b08014b703d1d920
    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 Nbe85993a7294459589f9aa8fada3b658
    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 N219eb66c1ec54988a1e38272e5d5e9a1 schema:name readcube_id
    35 schema:value 01566caf2b2c282eebc2c13bf1a69228d473e1bb49773f677dd9ada15352ab5b
    36 rdf:type schema:PropertyValue
    37 N35dbc9e6f9cd498a93a4a1b73856e839 schema:name dimensions_id
    38 schema:value pub.1000281398
    39 rdf:type schema:PropertyValue
    40 N50d2b3e241524539b08014b703d1d920 schema:location Berlin, Heidelberg
    41 schema:name Springer Berlin Heidelberg
    42 rdf:type schema:Organisation
    43 N7d32c360a6714f8398b14099cc887b13 rdf:first sg:person.015542102631.22
    44 rdf:rest Nc5f9a3f4e3974fdf9acc1e96b5cc204d
    45 N9f7afdf2e6c74b4595ac088c7f7cadad schema:isbn 978-3-540-62495-0
    46 978-3-540-68048-2
    47 schema:name Graph Drawing
    48 rdf:type schema:Book
    49 Nb0d7207353c6402bb5ccd94c41247ed4 rdf:first sg:person.01314347503.31
    50 rdf:rest N7d32c360a6714f8398b14099cc887b13
    51 Nb1c23e11dbc24f0c833c50f0ec18de6d schema:familyName North
    52 schema:givenName Stephen
    53 rdf:type schema:Person
    54 Nbe85993a7294459589f9aa8fada3b658 schema:name Springer Nature - SN SciGraph project
    55 rdf:type schema:Organization
    56 Nc5f9a3f4e3974fdf9acc1e96b5cc204d rdf:first sg:person.07560613205.66
    57 rdf:rest rdf:nil
    58 Ne81183bf65c1445ab1d3036a4b67d6a9 rdf:first Nb1c23e11dbc24f0c833c50f0ec18de6d
    59 rdf:rest rdf:nil
    60 Nfcbfadec2c454a8580e7f61e98524ad4 schema:name doi
    61 schema:value 10.1007/3-540-62495-3_44
    62 rdf:type schema:PropertyValue
    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)


    ...