# Optimal st-Orientations for Plane Triangulations

Ontology type: schema:Chapter

### Chapter Info

DATE

2007-01-01

AUTHORS ABSTRACT

For a plane triangulation G with n vertices, it has been proved that there exists a plane triangulation G with n vertices such that for any st-orientation of G, the length of the longest directed paths of G from s to t is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\geq \lfloor \frac{2n}{3}\rfloor$\end{document} [18] . In this paper, we prove the bound \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{2n}{3}$\end{document} is optimal by showing that every plane triangulation G with n-vertices admits an st-orientation with the length of its longest directed paths bounded by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac {2n}{3}+O(1)$\end{document}. In addition, this st-orientation is constructible in linear time. A by-product of this result is that every plane graph G with n vertices admits a visibility representation with height \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\le \frac{2n}{3}+O(1)$\end{document}, constructible in linear time, which is also optimal. More... »

PAGES

296-305

### Book

TITLE

Algorithmic Aspects in Information and Management

ISBN

978-3-540-72868-9
978-3-540-72870-2

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-72870-2_28

DOI

http://dx.doi.org/10.1007/978-3-540-72870-2_28

DIMENSIONS

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

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/11",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Medical and Health Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1117",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Public Health and Health Services",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Computer Science Department, University of Alabama in Huntsville, Huntsville, AL, 35899, USA",
"id": "http://www.grid.ac/institutes/grid.265893.3",
"name": [
"Computer Science Department, University of Alabama in Huntsville, Huntsville, AL, 35899, 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"
},
{
"affiliation": {
"alternateName": "Department of Computer Science and Engineering, SUNY at Buffalo, Buffalo, NY, 14260, USA",
"id": "http://www.grid.ac/institutes/grid.273335.3",
"name": [
"Department of Computer Science and Engineering, SUNY at Buffalo, Buffalo, NY, 14260, 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"
}
],
"datePublished": "2007-01-01",
"datePublishedReg": "2007-01-01",
"description": "For a plane triangulation G with n vertices, it has been proved that there exists a plane triangulation G with n vertices such that for any st-orientation of G, the length of the longest directed paths of G from s to t is \\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}$\\geq \\lfloor \\frac{2n}{3}\\rfloor$\\end{document} [18] . In this paper, we prove the bound \\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}$\\frac{2n}{3}$\\end{document} is optimal by showing that every plane triangulation G with n-vertices admits an st-orientation with the length of its longest directed paths bounded by \\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}$\\frac {2n}{3}+O(1)$\\end{document}. In addition, this st-orientation is constructible in linear time. A by-product of this result is that every plane graph G with n vertices admits a visibility representation with height \\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}$\\le \\frac{2n}{3}+O(1)$\\end{document}, constructible in linear time, which is also optimal.",
"editor": [
{
"familyName": "Kao",
"givenName": "Ming-Yang",
"type": "Person"
},
{
"familyName": "Li",
"givenName": "Xiang-Yang",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-540-72870-2_28",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-540-72868-9",
"978-3-540-72870-2"
],
"name": "Algorithmic Aspects in Information and Management",
"type": "Book"
},
"keywords": [
"time",
"length",
"results",
"height",
"products",
"triangulation",
"path",
"vertices",
"representation",
"paper",
"triangulation G",
"graph G",
"plane triangulations",
"linear time",
"plane triangulation G",
"plane graph G",
"visibility representation",
"Optimal st-Orientations",
"st-orientations"
],
"name": "Optimal st-Orientations for Plane Triangulations",
"pagination": "296-305",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1022421972"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-540-72870-2_28"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-540-72870-2_28",
"https://app.dimensions.ai/details/publication/pub.1022421972"
],
"sdDataset": "chapters",
"sdDatePublished": "2021-11-01T18:50",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_212.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-540-72870-2_28"
}
]

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-72870-2_28'

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-72870-2_28'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-72870-2_28'

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-72870-2_28'

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

95 TRIPLES      23 PREDICATES      45 URIs      38 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:1117
4 schema:datePublished 2007-01-01
5 schema:datePublishedReg 2007-01-01
6 schema:description For a plane triangulation G with n vertices, it has been proved that there exists a plane triangulation G with n vertices such that for any st-orientation of G, the length of the longest directed paths of G from s to t is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\geq \lfloor \frac{2n}{3}\rfloor$\end{document} [18] . In this paper, we prove the bound \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{2n}{3}$\end{document} is optimal by showing that every plane triangulation G with n-vertices admits an st-orientation with the length of its longest directed paths bounded by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac {2n}{3}+O(1)$\end{document}. In addition, this st-orientation is constructible in linear time. A by-product of this result is that every plane graph G with n vertices admits a visibility representation with height \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\le \frac{2n}{3}+O(1)$\end{document}, constructible in linear time, which is also optimal.
7 schema:editor Nc5d15e71076a499da7d62650412593f5
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nbbdef8bd807743b4974747f0885087a0
12 schema:keywords Optimal st-Orientations
14 graph G
15 height
16 length
17 linear time
18 paper
19 path
20 plane graph G
21 plane triangulation G
22 plane triangulations
23 products
24 representation
25 results
26 st-orientations
27 time
28 triangulation
29 triangulation G
30 vertices
31 visibility representation
32 schema:name Optimal st-Orientations for Plane Triangulations
33 schema:pagination 296-305
34 schema:productId N0fbc0b483abb484185e3db47c01a9196
35 N90c0e751774b4ae6bc969ff40e3f787f
36 schema:publisher N58b904c73150404a84c233ebbf072ec9
37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022421972
38 https://doi.org/10.1007/978-3-540-72870-2_28
39 schema:sdDatePublished 2021-11-01T18:50
41 schema:sdPublisher N5b14e1afb6fd432ba3555c3d52320d3d
42 schema:url https://doi.org/10.1007/978-3-540-72870-2_28
44 sgo:sdDataset chapters
45 rdf:type schema:Chapter
46 N0fbc0b483abb484185e3db47c01a9196 schema:name dimensions_id
47 schema:value pub.1022421972
48 rdf:type schema:PropertyValue
49 N34ddfde4682743d981a94cff9d13c34a schema:familyName Li
50 schema:givenName Xiang-Yang
51 rdf:type schema:Person
52 N58b904c73150404a84c233ebbf072ec9 schema:name Springer Nature
53 rdf:type schema:Organisation
54 N5b14e1afb6fd432ba3555c3d52320d3d schema:name Springer Nature - SN SciGraph project
55 rdf:type schema:Organization
56 N6b6f387a950b42768261ae43ed1e7a87 schema:familyName Kao
57 schema:givenName Ming-Yang
58 rdf:type schema:Person
59 N90c0e751774b4ae6bc969ff40e3f787f schema:name doi
60 schema:value 10.1007/978-3-540-72870-2_28
61 rdf:type schema:PropertyValue
63 rdf:rest Nc9eccc13c8614fd6bd2e7a3f94518745
64 Nbbdef8bd807743b4974747f0885087a0 schema:isbn 978-3-540-72868-9
65 978-3-540-72870-2
66 schema:name Algorithmic Aspects in Information and Management
67 rdf:type schema:Book
68 Nc5d15e71076a499da7d62650412593f5 rdf:first N6b6f387a950b42768261ae43ed1e7a87
69 rdf:rest Ncf7806b81d334232966a12a29d92e0a7
70 Nc9eccc13c8614fd6bd2e7a3f94518745 rdf:first sg:person.011352641523.42
71 rdf:rest rdf:nil
72 Ncf7806b81d334232966a12a29d92e0a7 rdf:first N34ddfde4682743d981a94cff9d13c34a
73 rdf:rest rdf:nil
74 anzsrc-for:11 schema:inDefinedTermSet anzsrc-for:
75 schema:name Medical and Health Sciences
76 rdf:type schema:DefinedTerm
77 anzsrc-for:1117 schema:inDefinedTermSet anzsrc-for:
78 schema:name Public Health and Health Services
79 rdf:type schema:DefinedTerm
80 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
81 schema:familyName He
82 schema:givenName Xin
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
84 rdf:type schema:Person
85 sg:person.012041227127.88 schema:affiliation grid-institutes:grid.265893.3
86 schema:familyName Zhang
87 schema:givenName Huaming
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88
89 rdf:type schema:Person
90 grid-institutes:grid.265893.3 schema:alternateName Computer Science Department, University of Alabama in Huntsville, Huntsville, AL, 35899, USA
91 schema:name Computer Science Department, University of Alabama in Huntsville, Huntsville, AL, 35899, USA
92 rdf:type schema:Organization
93 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science and Engineering, SUNY at Buffalo, Buffalo, NY, 14260, USA
94 schema:name Department of Computer Science and Engineering, SUNY at Buffalo, Buffalo, NY, 14260, USA
95 rdf:type schema:Organization