# On Succinct Greedy Drawings of Plane Triangulations and 3-Connected Plane Graphs

Ontology type: schema:ScholarlyArticle

### Article Info

DATE

2012-08-25

AUTHORS ABSTRACT

Geometric routing by using virtual locations is an elegant way for solving network routing problems. In its simplest form, greedy routing, a message is simply forwarded to a neighbor that is closer to the destination. It has been an open conjecture whether every 3-connected plane graph has a greedy drawing in the Euclidean plane R2 (by Papadimitriou and Ratajczak in Theor. Comp. Sci. 344(1):3–14, 2005). Leighton and Moitra (Discrete Comput. Geom. 44(3):686–705, 2010) recently settled this conjecture positively. One main drawback of this approach is that the coordinates of the virtual locations require Ω(nlogn) bits to represent (the same space usage as traditional routing table approaches). This makes greedy routing infeasible in applications.In this paper, we show that the classical Schnyder drawing in R2 of plane triangulations is greedy with respect to a simple natural metric function H(u,v) over R2 that is equivalent to Euclidean metric DE(u,v) (in the sense that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$D_{E}(u,v) \leq H(u,v) \leq2\sqrt{2}D_{E}(u,v)$\end{document}). The drawing uses two integer coordinates between 0 and 2n−5, which can be represented by logn bits. We also show that the classical Schnyder drawing in R2 of 3-connected plane graphs is weakly greedy with respect to the same metric function H(∗,∗). The drawing uses two integer coordinates between 0 and f (where f is the number of internal faces of G). More... »

PAGES

531-544

### References to SciGraph publications

• 2003-06. Geodesic Embeddings and Planar Graphs in ORDER
• 2009. Succinct Greedy Geometric Routing in the Euclidean Plane in ALGORITHMS AND COMPUTATION
• 2009-10-20. Some Results on Greedy Embeddings in Metric Spaces in DISCRETE & COMPUTATIONAL GEOMETRY
• 2010. Schnyder Greedy Routing Algorithm in THEORY AND APPLICATIONS OF MODELS OF COMPUTATION
• 2008-01-01. On the Efficiency of a Local Iterative Algorithm to Compute Delaunay Realizations in EXPERIMENTAL ALGORITHMS
• 1999-04. Output-Sensitive Reporting of Disjoint Paths in ALGORITHMICA
• 2009-12-29. Greedy Drawings of Triangulations in DISCRETE & COMPUTATIONAL GEOMETRY
• 2007-09-12. Schnyder Woods and Orthogonal Surfaces in DISCRETE & COMPUTATIONAL GEOMETRY
• 2009-04-22. Schnyder Woods for Higher Genus Triangulated Surfaces, with Applications to Encoding in DISCRETE & COMPUTATIONAL GEOMETRY
• 2001-03. Convex Drawings of Planar Graphs and the Order Dimension of 3-Polytopes in ORDER
• 2007-02-09. Convex Drawings of 3-Connected Plane Graphs in ALGORITHMICA
• 2009. On Convex Greedy Embedding Conjecture for 3-Connected Planar Graphs in FUNDAMENTALS OF COMPUTATION THEORY
• 1989-12. Planar graphs and poset dimension in ORDER

TITLE

Algorithmica

ISSUE

2

VOLUME

68

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-012-9682-y

DOI

http://dx.doi.org/10.1007/s00453-012-9682-y

DIMENSIONS

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

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:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"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"
},
{
"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"
}
],
"author": [
{
"affiliation": {
"alternateName": "Department of Computer Science and Engineering, State University of New York at Buffalo, 14260, Buffalo, NY, USA",
"id": "http://www.grid.ac/institutes/grid.273335.3",
"name": [
"Department of Computer Science and Engineering, State University of New York at Buffalo, 14260, Buffalo, NY, USA"
],
"type": "Organization"
},
"familyName": "He",
"givenName": "Xin",
"id": "sg:person.011352641523.42",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Computer Science Department, The University of Alabama in Huntsville, 35899, Huntsville, AL, USA",
"id": "http://www.grid.ac/institutes/grid.265893.3",
"name": [
"Computer Science Department, The University of Alabama in Huntsville, 35899, Huntsville, AL, USA"
],
"type": "Organization"
},
"familyName": "Zhang",
"givenName": "Huaming",
"id": "sg:person.012041227127.88",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1023/b:orde.0000009251.68514.8b",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1011414632",
"https://doi.org/10.1023/b:orde.0000009251.68514.8b"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1023/a:1010604726900",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039535785",
"https://doi.org/10.1023/a:1010604726900"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-03409-1_14",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1028664149",
"https://doi.org/10.1007/978-3-642-03409-1_14"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-68552-4_6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1045752938",
"https://doi.org/10.1007/978-3-540-68552-4_6"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00454-007-9027-9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1018260767",
"https://doi.org/10.1007/s00454-007-9027-9"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00453-006-0177-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1048749374",
"https://doi.org/10.1007/s00453-006-0177-6"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-10631-6_79",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1047174233",
"https://doi.org/10.1007/978-3-642-10631-6_79"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-13562-0_25",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1009749616",
"https://doi.org/10.1007/978-3-642-13562-0_25"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00454-009-9169-z",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043130774",
"https://doi.org/10.1007/s00454-009-9169-z"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00454-009-9227-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1006354063",
"https://doi.org/10.1007/s00454-009-9227-6"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00454-009-9235-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1030630709",
"https://doi.org/10.1007/s00454-009-9235-6"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf00353652",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1015637021",
"https://doi.org/10.1007/bf00353652"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/pl00009264",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1027274991",
"https://doi.org/10.1007/pl00009264"
],
"type": "CreativeWork"
}
],
"datePublished": "2012-08-25",
"datePublishedReg": "2012-08-25",
"description": "Geometric routing by using virtual locations is an elegant way for solving network routing problems. In its simplest form, greedy routing, a message is simply forwarded to a neighbor that is closer to the destination. It has been an open conjecture whether every 3-connected plane graph has a greedy drawing in the Euclidean plane R2 (by Papadimitriou and Ratajczak in Theor. Comp. Sci. 344(1):3\u201314, 2005). Leighton and Moitra (Discrete Comput. Geom. 44(3):686\u2013705, 2010) recently settled this conjecture positively. One main drawback of this approach is that the coordinates of the virtual locations require \u03a9(nlogn) bits to represent (the same space usage as traditional routing table approaches). This makes greedy routing infeasible in applications.In this paper, we show that the classical Schnyder drawing in R2 of plane triangulations is greedy with respect to a simple natural metric function H(u,v) over R2 that is equivalent to Euclidean metric DE(u,v) (in the sense that \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$D_{E}(u,v) \\leq H(u,v) \\leq2\\sqrt{2}D_{E}(u,v)$\\end{document}). The drawing uses two integer coordinates between 0 and 2n\u22125, which can be represented by logn bits. We also show that the classical Schnyder drawing in R2 of 3-connected plane graphs is weakly greedy with respect to the same metric function H(\u2217,\u2217). The drawing uses two integer coordinates between 0 and\u00a0f (where f is the number of internal faces of G).",
"genre": "article",
"id": "sg:pub.10.1007/s00453-012-9682-y",
"inLanguage": "en",
"isAccessibleForFree": false,
"isFundedItemOf": [
{
"id": "sg:grant.3072157",
"type": "MonetaryGrant"
},
{
"id": "sg:grant.3115487",
"type": "MonetaryGrant"
}
],
"isPartOf": [
{
"id": "sg:journal.1047644",
"issn": [
"0178-4617",
"1432-0541"
],
"name": "Algorithmica",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "2",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
}
],
"keywords": [
"virtual locations",
"greedy drawing",
"network routing problem",
"geometric routing",
"logn bits",
"greedy routing",
"routing problem",
"metric functions",
"routing",
"elegant way",
"graph",
"main drawback",
"integer coordinates",
"bits",
"plane graph",
"plane triangulations",
"triangulation",
"messages",
"drawings",
"neighbors",
"open conjecture",
"Moitra",
"coordinates",
"destination",
"drawbacks",
"Euclidean",
"Euclidean plane R2",
"applications",
"simple form",
"location",
"Leighton",
"way",
"respect",
"function",
"conjecture",
"plane R2",
"R2",
"form",
"paper",
"problem",
"approach",
"classical Schnyder drawing",
"Schnyder drawing",
"simple natural metric function",
"natural metric function",
"same metric function",
"Succinct Greedy Drawings"
],
"name": "On Succinct Greedy Drawings of Plane Triangulations and 3-Connected Plane Graphs",
"pagination": "531-544",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1041463098"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00453-012-9682-y"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00453-012-9682-y",
"https://app.dimensions.ai/details/publication/pub.1041463098"
],
"sdDataset": "articles",
"sdDatePublished": "2021-12-01T19:26",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/article/article_565.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00453-012-9682-y"
}
]

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/s00453-012-9682-y'

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/s00453-012-9682-y'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-012-9682-y'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-012-9682-y'

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

171 TRIPLES      22 PREDICATES      85 URIs      64 LITERALS      6 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author Nb37195ddba9947de9c2b4e760d902f6e
4 schema:citation sg:pub.10.1007/978-3-540-68552-4_6
5 sg:pub.10.1007/978-3-642-03409-1_14
6 sg:pub.10.1007/978-3-642-10631-6_79
7 sg:pub.10.1007/978-3-642-13562-0_25
8 sg:pub.10.1007/bf00353652
9 sg:pub.10.1007/pl00009264
10 sg:pub.10.1007/s00453-006-0177-6
11 sg:pub.10.1007/s00454-007-9027-9
12 sg:pub.10.1007/s00454-009-9169-z
13 sg:pub.10.1007/s00454-009-9227-6
14 sg:pub.10.1007/s00454-009-9235-6
15 sg:pub.10.1023/a:1010604726900
16 sg:pub.10.1023/b:orde.0000009251.68514.8b
17 schema:datePublished 2012-08-25
18 schema:datePublishedReg 2012-08-25
19 schema:description Geometric routing by using virtual locations is an elegant way for solving network routing problems. In its simplest form, greedy routing, a message is simply forwarded to a neighbor that is closer to the destination. It has been an open conjecture whether every 3-connected plane graph has a greedy drawing in the Euclidean plane R2 (by Papadimitriou and Ratajczak in Theor. Comp. Sci. 344(1):3–14, 2005). Leighton and Moitra (Discrete Comput. Geom. 44(3):686–705, 2010) recently settled this conjecture positively. One main drawback of this approach is that the coordinates of the virtual locations require Ω(nlogn) bits to represent (the same space usage as traditional routing table approaches). This makes greedy routing infeasible in applications.In this paper, we show that the classical Schnyder drawing in R2 of plane triangulations is greedy with respect to a simple natural metric function H(u,v) over R2 that is equivalent to Euclidean metric DE(u,v) (in the sense that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$D_{E}(u,v) \leq H(u,v) \leq2\sqrt{2}D_{E}(u,v)$\end{document}). The drawing uses two integer coordinates between 0 and 2n−5, which can be represented by logn bits. We also show that the classical Schnyder drawing in R2 of 3-connected plane graphs is weakly greedy with respect to the same metric function H(∗,∗). The drawing uses two integer coordinates between 0 and f (where f is the number of internal faces of G).
20 schema:genre article
21 schema:inLanguage en
22 schema:isAccessibleForFree false
23 schema:isPartOf N437506baf80442d1892484e6e3608429
24 N61dab44e0fe941b19f21de610a2afb46
25 sg:journal.1047644
26 schema:keywords Euclidean
27 Euclidean plane R2
28 Leighton
29 Moitra
30 R2
31 Schnyder drawing
32 Succinct Greedy Drawings
33 applications
34 approach
35 bits
36 classical Schnyder drawing
37 conjecture
38 coordinates
39 destination
40 drawbacks
41 drawings
42 elegant way
43 form
44 function
45 geometric routing
46 graph
47 greedy drawing
48 greedy routing
49 integer coordinates
50 location
51 logn bits
52 main drawback
53 messages
54 metric functions
55 natural metric function
56 neighbors
57 network routing problem
58 open conjecture
59 paper
60 plane R2
61 plane graph
62 plane triangulations
63 problem
64 respect
65 routing
66 routing problem
67 same metric function
68 simple form
69 simple natural metric function
70 triangulation
71 virtual locations
72 way
73 schema:name On Succinct Greedy Drawings of Plane Triangulations and 3-Connected Plane Graphs
74 schema:pagination 531-544
75 schema:productId N858484ce56b64f77af30f538fdb59b86
76 Nbc4ef70b38cf4efc83e6f1b62592e99a
77 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041463098
78 https://doi.org/10.1007/s00453-012-9682-y
79 schema:sdDatePublished 2021-12-01T19:26
82 schema:url https://doi.org/10.1007/s00453-012-9682-y
84 sgo:sdDataset articles
85 rdf:type schema:ScholarlyArticle
86 N437506baf80442d1892484e6e3608429 schema:issueNumber 2
87 rdf:type schema:PublicationIssue
89 rdf:type schema:PublicationVolume
90 N858484ce56b64f77af30f538fdb59b86 schema:name doi
91 schema:value 10.1007/s00453-012-9682-y
92 rdf:type schema:PropertyValue
94 rdf:type schema:Organization
95 Nb37195ddba9947de9c2b4e760d902f6e rdf:first sg:person.011352641523.42
96 rdf:rest Nb7193d8a0d1b4593b3c12604cd1a79df
97 Nb7193d8a0d1b4593b3c12604cd1a79df rdf:first sg:person.012041227127.88
98 rdf:rest rdf:nil
99 Nbc4ef70b38cf4efc83e6f1b62592e99a schema:name dimensions_id
100 schema:value pub.1041463098
101 rdf:type schema:PropertyValue
102 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
103 schema:name Information and Computing Sciences
104 rdf:type schema:DefinedTerm
105 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
106 schema:name Computation Theory and Mathematics
107 rdf:type schema:DefinedTerm
108 sg:grant.3072157 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-012-9682-y
109 rdf:type schema:MonetaryGrant
110 sg:grant.3115487 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-012-9682-y
111 rdf:type schema:MonetaryGrant
112 sg:journal.1047644 schema:issn 0178-4617
113 1432-0541
114 schema:name Algorithmica
115 schema:publisher Springer Nature
116 rdf:type schema:Periodical
117 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
118 schema:familyName He
119 schema:givenName Xin
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
121 rdf:type schema:Person
122 sg:person.012041227127.88 schema:affiliation grid-institutes:grid.265893.3
123 schema:familyName Zhang
124 schema:givenName Huaming
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88
126 rdf:type schema:Person
127 sg:pub.10.1007/978-3-540-68552-4_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045752938
128 https://doi.org/10.1007/978-3-540-68552-4_6
129 rdf:type schema:CreativeWork
130 sg:pub.10.1007/978-3-642-03409-1_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028664149
131 https://doi.org/10.1007/978-3-642-03409-1_14
132 rdf:type schema:CreativeWork
133 sg:pub.10.1007/978-3-642-10631-6_79 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047174233
134 https://doi.org/10.1007/978-3-642-10631-6_79
135 rdf:type schema:CreativeWork
136 sg:pub.10.1007/978-3-642-13562-0_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009749616
137 https://doi.org/10.1007/978-3-642-13562-0_25
138 rdf:type schema:CreativeWork
139 sg:pub.10.1007/bf00353652 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015637021
140 https://doi.org/10.1007/bf00353652
141 rdf:type schema:CreativeWork
142 sg:pub.10.1007/pl00009264 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027274991
143 https://doi.org/10.1007/pl00009264
144 rdf:type schema:CreativeWork
145 sg:pub.10.1007/s00453-006-0177-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048749374
146 https://doi.org/10.1007/s00453-006-0177-6
147 rdf:type schema:CreativeWork
148 sg:pub.10.1007/s00454-007-9027-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018260767
149 https://doi.org/10.1007/s00454-007-9027-9
150 rdf:type schema:CreativeWork
151 sg:pub.10.1007/s00454-009-9169-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1043130774
152 https://doi.org/10.1007/s00454-009-9169-z
153 rdf:type schema:CreativeWork
154 sg:pub.10.1007/s00454-009-9227-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006354063
155 https://doi.org/10.1007/s00454-009-9227-6
156 rdf:type schema:CreativeWork
157 sg:pub.10.1007/s00454-009-9235-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030630709
158 https://doi.org/10.1007/s00454-009-9235-6
159 rdf:type schema:CreativeWork
160 sg:pub.10.1023/a:1010604726900 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039535785
161 https://doi.org/10.1023/a:1010604726900
162 rdf:type schema:CreativeWork
163 sg:pub.10.1023/b:orde.0000009251.68514.8b schema:sameAs https://app.dimensions.ai/details/publication/pub.1011414632
164 https://doi.org/10.1023/b:orde.0000009251.68514.8b
165 rdf:type schema:CreativeWork
166 grid-institutes:grid.265893.3 schema:alternateName Computer Science Department, The University of Alabama in Huntsville, 35899, Huntsville, AL, USA
167 schema:name Computer Science Department, The University of Alabama in Huntsville, 35899, Huntsville, AL, USA
168 rdf:type schema:Organization
169 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science and Engineering, State University of New York at Buffalo, 14260, Buffalo, NY, USA
170 schema:name Department of Computer Science and Engineering, State University of New York at Buffalo, 14260, Buffalo, NY, USA
171 rdf:type schema:Organization