On a Conjecture Related to Geometric Routing View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2004

AUTHORS

Christos H. Papadimitriou , David Ratajczak

ABSTRACT

We conjecture that any planar 3-connected graph can be embedded in the plane in such a way that for any nodes s and t, there is a path from s to t such that the Euclidean distance to t decreases monotonically along the path. A consequence of this conjecture would be that in any ad hoc network containing such a graph as a subgraph, 2-dimensional virtual coordinates for the nodes can be found for which greedy geographic routing is guaranteed to work. We discuss this conjecture and its equivalent forms. We show a weaker result, namely that for any network containing a 3-connected planar subgraph, 3-dimensional virtual coordinates always exist enabling a form of greedy routing inspired by the simplex method; we provide experimental evidence that this scheme is quite effective in practice. We also propose a rigorous form of face routing based on the Koebe-Andre’ev-Thurston theorem. Finally, we show a result delimiting the applicability of our approach: any 3-connected K3,3-free graph has a planar 3-connected subgraph. More... »

PAGES

9-17

Book

TITLE

Algorithmic Aspects of Wireless Sensor Networks

ISBN

978-3-540-22476-1
978-3-540-27820-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-27820-7_3

DOI

http://dx.doi.org/10.1007/978-3-540-27820-7_3

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Computer Science Division, University of California at Berkeley, 94720-1776, Berkeley, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "Computer Science Division, University of California at Berkeley, 94720-1776, Berkeley, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Papadimitriou", 
        "givenName": "Christos H.", 
        "id": "sg:person.013233165465.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Division, University of California at Berkeley, 94720-1776, Berkeley, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "Computer Science Division, University of California at Berkeley, 94720-1776, Berkeley, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ratajczak", 
        "givenName": "David", 
        "id": "sg:person.012236542671.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012236542671.05"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "We conjecture that any planar 3-connected graph can be embedded in the plane in such a way that for any nodes s and t, there is a path from s to t such that the Euclidean distance to t decreases monotonically along the path. A consequence of this conjecture would be that in any ad hoc network containing such a graph as a subgraph, 2-dimensional virtual coordinates for the nodes can be found for which greedy geographic routing is guaranteed to work. We discuss this conjecture and its equivalent forms. We show a weaker result, namely that for any network containing a 3-connected planar subgraph, 3-dimensional virtual coordinates always exist enabling a form of greedy routing inspired by the simplex method; we provide experimental evidence that this scheme is quite effective in practice. We also propose a rigorous form of face routing based on the Koebe-Andre\u2019ev-Thurston theorem. Finally, we show a result delimiting the applicability of our approach: any 3-connected K3,3-free graph has a planar 3-connected subgraph.", 
    "editor": [
      {
        "familyName": "Nikoletseas", 
        "givenName": "Sotiris E.", 
        "type": "Person"
      }, 
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9 D. P.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-27820-7_3", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-22476-1", 
        "978-3-540-27820-7"
      ], 
      "name": "Algorithmic Aspects of Wireless Sensor Networks", 
      "type": "Book"
    }, 
    "keywords": [
      "virtual coordinates", 
      "greedy geographic routing", 
      "geometric routing", 
      "face routing", 
      "geographic routing", 
      "greedy routing", 
      "planar 3-connected graphs", 
      "planar subgraph", 
      "routing", 
      "Euclidean distance", 
      "node s", 
      "graph", 
      "subgraphs", 
      "network", 
      "Thurston theorem", 
      "simplex method", 
      "path", 
      "nodes", 
      "scheme", 
      "equivalent form", 
      "coordinates", 
      "applicability", 
      "way", 
      "method", 
      "results", 
      "weaker results", 
      "distance", 
      "rigorous form", 
      "conjecture", 
      "form", 
      "theorem", 
      "practice", 
      "plane", 
      "consequences", 
      "experimental evidence", 
      "evidence", 
      "decrease", 
      "approach", 
      "Koebe-Andre\u2019ev", 
      "planar 3-connected subgraph"
    ], 
    "name": "On a Conjecture Related to Geometric Routing", 
    "pagination": "9-17", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1005783782"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-27820-7_3"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-27820-7_3", 
      "https://app.dimensions.ai/details/publication/pub.1005783782"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T19:57", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_162.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-27820-7_3"
  }
]
 

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/978-3-540-27820-7_3'

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/978-3-540-27820-7_3'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-27820-7_3'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-27820-7_3'


 

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

112 TRIPLES      23 PREDICATES      66 URIs      59 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-27820-7_3 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N51f087f216b44606b72b8031040403a5
4 schema:datePublished 2004
5 schema:datePublishedReg 2004-01-01
6 schema:description We conjecture that any planar 3-connected graph can be embedded in the plane in such a way that for any nodes s and t, there is a path from s to t such that the Euclidean distance to t decreases monotonically along the path. A consequence of this conjecture would be that in any ad hoc network containing such a graph as a subgraph, 2-dimensional virtual coordinates for the nodes can be found for which greedy geographic routing is guaranteed to work. We discuss this conjecture and its equivalent forms. We show a weaker result, namely that for any network containing a 3-connected planar subgraph, 3-dimensional virtual coordinates always exist enabling a form of greedy routing inspired by the simplex method; we provide experimental evidence that this scheme is quite effective in practice. We also propose a rigorous form of face routing based on the Koebe-Andre’ev-Thurston theorem. Finally, we show a result delimiting the applicability of our approach: any 3-connected K3,3-free graph has a planar 3-connected subgraph.
7 schema:editor N7c8304654d3744dcb5e8289ffcd224bd
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N57dc48a7752c4cecbb127a5c3e4a6810
12 schema:keywords Euclidean distance
13 Koebe-Andre’ev
14 Thurston theorem
15 applicability
16 approach
17 conjecture
18 consequences
19 coordinates
20 decrease
21 distance
22 equivalent form
23 evidence
24 experimental evidence
25 face routing
26 form
27 geographic routing
28 geometric routing
29 graph
30 greedy geographic routing
31 greedy routing
32 method
33 network
34 node s
35 nodes
36 path
37 planar 3-connected graphs
38 planar 3-connected subgraph
39 planar subgraph
40 plane
41 practice
42 results
43 rigorous form
44 routing
45 scheme
46 simplex method
47 subgraphs
48 theorem
49 virtual coordinates
50 way
51 weaker results
52 schema:name On a Conjecture Related to Geometric Routing
53 schema:pagination 9-17
54 schema:productId N7ce1962039ab4a4a8f47660cec55b103
55 Ne64d75770f084ecdb2ab2ec6a6575833
56 schema:publisher Ne4c7afb784154dc6b7a16e6a5fc29fe6
57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005783782
58 https://doi.org/10.1007/978-3-540-27820-7_3
59 schema:sdDatePublished 2021-12-01T19:57
60 schema:sdLicense https://scigraph.springernature.com/explorer/license/
61 schema:sdPublisher N77c5f57dd7f54481b425e79c34935910
62 schema:url https://doi.org/10.1007/978-3-540-27820-7_3
63 sgo:license sg:explorer/license/
64 sgo:sdDataset chapters
65 rdf:type schema:Chapter
66 N1d82a14ac8d642ebba7eb00d6cc84b15 schema:familyName Rolim
67 schema:givenName José D. P.
68 rdf:type schema:Person
69 N354f45d6b9fb4845bf9827ad9c7badf5 schema:familyName Nikoletseas
70 schema:givenName Sotiris E.
71 rdf:type schema:Person
72 N51f087f216b44606b72b8031040403a5 rdf:first sg:person.013233165465.63
73 rdf:rest Na6f59e7b078c47f590eb9ffc51fa7bcd
74 N57dc48a7752c4cecbb127a5c3e4a6810 schema:isbn 978-3-540-22476-1
75 978-3-540-27820-7
76 schema:name Algorithmic Aspects of Wireless Sensor Networks
77 rdf:type schema:Book
78 N77c5f57dd7f54481b425e79c34935910 schema:name Springer Nature - SN SciGraph project
79 rdf:type schema:Organization
80 N7c8304654d3744dcb5e8289ffcd224bd rdf:first N354f45d6b9fb4845bf9827ad9c7badf5
81 rdf:rest N84ba6e1de62d491db140b08b4cf4c01e
82 N7ce1962039ab4a4a8f47660cec55b103 schema:name dimensions_id
83 schema:value pub.1005783782
84 rdf:type schema:PropertyValue
85 N84ba6e1de62d491db140b08b4cf4c01e rdf:first N1d82a14ac8d642ebba7eb00d6cc84b15
86 rdf:rest rdf:nil
87 Na6f59e7b078c47f590eb9ffc51fa7bcd rdf:first sg:person.012236542671.05
88 rdf:rest rdf:nil
89 Ne4c7afb784154dc6b7a16e6a5fc29fe6 schema:name Springer Nature
90 rdf:type schema:Organisation
91 Ne64d75770f084ecdb2ab2ec6a6575833 schema:name doi
92 schema:value 10.1007/978-3-540-27820-7_3
93 rdf:type schema:PropertyValue
94 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
95 schema:name Mathematical Sciences
96 rdf:type schema:DefinedTerm
97 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
98 schema:name Pure Mathematics
99 rdf:type schema:DefinedTerm
100 sg:person.012236542671.05 schema:affiliation grid-institutes:grid.47840.3f
101 schema:familyName Ratajczak
102 schema:givenName David
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012236542671.05
104 rdf:type schema:Person
105 sg:person.013233165465.63 schema:affiliation grid-institutes:grid.47840.3f
106 schema:familyName Papadimitriou
107 schema:givenName Christos H.
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63
109 rdf:type schema:Person
110 grid-institutes:grid.47840.3f schema:alternateName Computer Science Division, University of California at Berkeley, 94720-1776, Berkeley, CA, USA
111 schema:name Computer Science Division, University of California at Berkeley, 94720-1776, Berkeley, CA, USA
112 rdf:type schema:Organization
 




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


...