On the computational complexity of upward and rectilinear planarity testing View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1995

AUTHORS

Ashim Garg , Roberto Tamassia

ABSTRACT

A directed graph is upward planar if it can be drawn in the plane such that every edge is a monotonically increasing curve in the vertical direction, and no two edges cross. An undirected graph is rectilinear planar if it can be drawn in the plane such that every edge is a horizontal or vertical segment, and no two edges cross. Testing upward planarity and rectilinear planarity are fundamental problems in the effective visualization of various graph and network structures. In this paper we show that upward planarity testing and rectilinear planarity testing are NP-complete problems. We also show that it is NP-hard to approximate the minimum number of bends in a planar orthogonal drawing of an n-vertex graph with an O(n 1−∈) error, for any ∈>0. More... »

PAGES

286-297

Book

TITLE

Graph Drawing

ISBN

978-3-540-58950-1
978-3-540-49155-2

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-58950-3_384

DOI

http://dx.doi.org/10.1007/3-540-58950-3_384

DIMENSIONS

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


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": "Brown University", 
          "id": "https://www.grid.ac/institutes/grid.40263.33", 
          "name": [
            "Department of Computer Science, Brown University, 02912-1910\u00a0Providence, RI, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Garg", 
        "givenName": "Ashim", 
        "id": "sg:person.013377047435.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013377047435.30"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Brown University", 
          "id": "https://www.grid.ac/institutes/grid.40263.33", 
          "name": [
            "Department of Computer Science, Brown University, 02912-1910\u00a0Providence, RI, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tamassia", 
        "givenName": "Roberto", 
        "id": "sg:person.0674326220.33", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0674326220.33"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1995", 
    "datePublishedReg": "1995-01-01", 
    "description": "A directed graph is upward planar if it can be drawn in the plane such that every edge is a monotonically increasing curve in the vertical direction, and no two edges cross. An undirected graph is rectilinear planar if it can be drawn in the plane such that every edge is a horizontal or vertical segment, and no two edges cross. Testing upward planarity and rectilinear planarity are fundamental problems in the effective visualization of various graph and network structures. In this paper we show that upward planarity testing and rectilinear planarity testing are NP-complete problems. We also show that it is NP-hard to approximate the minimum number of bends in a planar orthogonal drawing of an n-vertex graph with an O(n 1\u2212\u2208) error, for any \u2208>0.", 
    "editor": [
      {
        "familyName": "Tamassia", 
        "givenName": "Roberto", 
        "type": "Person"
      }, 
      {
        "familyName": "Tollis", 
        "givenName": "Ioannis G.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-58950-3_384", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-58950-1", 
        "978-3-540-49155-2"
      ], 
      "name": "Graph Drawing", 
      "type": "Book"
    }, 
    "name": "On the computational complexity of upward and rectilinear planarity testing", 
    "pagination": "286-297", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-58950-3_384"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "9426ea73d570b72671fa14d730b55ab87247604609e6126ae321c7845915f6e2"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1031098794"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-58950-3_384", 
      "https://app.dimensions.ai/details/publication/pub.1031098794"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T12:18", 
    "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_8663_00000053.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-58950-3_384"
  }
]
 

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-58950-3_384'

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-58950-3_384'

Turtle is a human-readable linked data format.

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

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-58950-3_384'


 

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

77 TRIPLES      22 PREDICATES      27 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-58950-3_384 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Ncbd82a85d6ba4ad49ca3edf22d2526a5
4 schema:datePublished 1995
5 schema:datePublishedReg 1995-01-01
6 schema:description A directed graph is upward planar if it can be drawn in the plane such that every edge is a monotonically increasing curve in the vertical direction, and no two edges cross. An undirected graph is rectilinear planar if it can be drawn in the plane such that every edge is a horizontal or vertical segment, and no two edges cross. Testing upward planarity and rectilinear planarity are fundamental problems in the effective visualization of various graph and network structures. In this paper we show that upward planarity testing and rectilinear planarity testing are NP-complete problems. We also show that it is NP-hard to approximate the minimum number of bends in a planar orthogonal drawing of an n-vertex graph with an O(n 1−∈) error, for any ∈>0.
7 schema:editor Na8870c23f60e4109a1fba1d5aefa44af
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nd870afc682d944beada1e77b374e324c
12 schema:name On the computational complexity of upward and rectilinear planarity testing
13 schema:pagination 286-297
14 schema:productId N197ce951221c4bada6182ff2fd8971ba
15 N37c2e9293c4549f6893662c2eaaede1c
16 Nb0d4414ca22741ee98e06f940dd034af
17 schema:publisher N16a5423d7b394ca2a0a0629adb1024a3
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031098794
19 https://doi.org/10.1007/3-540-58950-3_384
20 schema:sdDatePublished 2019-04-15T12:18
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher N5437ea87370f41d288af0334fa9a0e00
23 schema:url http://link.springer.com/10.1007/3-540-58950-3_384
24 sgo:license sg:explorer/license/
25 sgo:sdDataset chapters
26 rdf:type schema:Chapter
27 N16a5423d7b394ca2a0a0629adb1024a3 schema:location Berlin, Heidelberg
28 schema:name Springer Berlin Heidelberg
29 rdf:type schema:Organisation
30 N197ce951221c4bada6182ff2fd8971ba schema:name dimensions_id
31 schema:value pub.1031098794
32 rdf:type schema:PropertyValue
33 N37c2e9293c4549f6893662c2eaaede1c schema:name readcube_id
34 schema:value 9426ea73d570b72671fa14d730b55ab87247604609e6126ae321c7845915f6e2
35 rdf:type schema:PropertyValue
36 N5437ea87370f41d288af0334fa9a0e00 schema:name Springer Nature - SN SciGraph project
37 rdf:type schema:Organization
38 Na5507196226c40a8aafcd556ff57a0e0 schema:familyName Tamassia
39 schema:givenName Roberto
40 rdf:type schema:Person
41 Na5e2e8a47c6244bb9f0e43477edde8d1 rdf:first Nc5f863ceaa7548d881972f76e6c1959a
42 rdf:rest rdf:nil
43 Na8870c23f60e4109a1fba1d5aefa44af rdf:first Na5507196226c40a8aafcd556ff57a0e0
44 rdf:rest Na5e2e8a47c6244bb9f0e43477edde8d1
45 Nb0d4414ca22741ee98e06f940dd034af schema:name doi
46 schema:value 10.1007/3-540-58950-3_384
47 rdf:type schema:PropertyValue
48 Nb932289a6758446c946b45f19a61a9c4 rdf:first sg:person.0674326220.33
49 rdf:rest rdf:nil
50 Nc5f863ceaa7548d881972f76e6c1959a schema:familyName Tollis
51 schema:givenName Ioannis G.
52 rdf:type schema:Person
53 Ncbd82a85d6ba4ad49ca3edf22d2526a5 rdf:first sg:person.013377047435.30
54 rdf:rest Nb932289a6758446c946b45f19a61a9c4
55 Nd870afc682d944beada1e77b374e324c schema:isbn 978-3-540-49155-2
56 978-3-540-58950-1
57 schema:name Graph Drawing
58 rdf:type schema:Book
59 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
60 schema:name Information and Computing Sciences
61 rdf:type schema:DefinedTerm
62 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
63 schema:name Computation Theory and Mathematics
64 rdf:type schema:DefinedTerm
65 sg:person.013377047435.30 schema:affiliation https://www.grid.ac/institutes/grid.40263.33
66 schema:familyName Garg
67 schema:givenName Ashim
68 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013377047435.30
69 rdf:type schema:Person
70 sg:person.0674326220.33 schema:affiliation https://www.grid.ac/institutes/grid.40263.33
71 schema:familyName Tamassia
72 schema:givenName Roberto
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0674326220.33
74 rdf:type schema:Person
75 https://www.grid.ac/institutes/grid.40263.33 schema:alternateName Brown University
76 schema:name Department of Computer Science, Brown University, 02912-1910 Providence, RI, USA
77 rdf:type schema:Organization
 




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


...