# Optimal st-orientations for plane triangulations

Ontology type: schema:ScholarlyArticle

### Article Info

DATE

2007-11-22

AUTHORS ABSTRACT

For plane triangulations, 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 in the st-orientation 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} (Zhang and He in Lecture Notes in Computer Science, vol. 3383, pp. 425–430, 2005). 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

367-377

### Journal

TITLE

Journal of Combinatorial Optimization

ISSUE

4

VOLUME

17

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10878-007-9119-8

DOI

http://dx.doi.org/10.1007/s10878-007-9119-8

DIMENSIONS

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

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/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"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Applied Mathematics",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Numerical and Computational Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA",
"id": "http://www.grid.ac/institutes/grid.265893.3",
"name": [
"Computer Science Department, 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"
},
{
"affiliation": {
"alternateName": "Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Buffalo, NY, USA",
"id": "http://www.grid.ac/institutes/grid.273335.3",
"name": [
"Department of Computer Science and Engineering, SUNY 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"
}
],
"citation": [
{
"id": "sg:pub.10.1007/11618058_32",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1033094987",
"https://doi.org/10.1007/11618058_32"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11786986_36",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017247286",
"https://doi.org/10.1007/11786986_36"
],
"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/bf02187706",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1008881195",
"https://doi.org/10.1007/bf02187706"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02253293",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1018365863",
"https://doi.org/10.1007/bf02253293"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02187705",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1027312329",
"https://doi.org/10.1007/bf02187705"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-31843-9_43",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1003846466",
"https://doi.org/10.1007/978-3-540-31843-9_43"
],
"type": "CreativeWork"
}
],
"datePublished": "2007-11-22",
"datePublishedReg": "2007-11-22",
"description": "Abstract\nFor plane triangulations, 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 in the st-orientation is \n\\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} \n(Zhang and He in Lecture Notes in Computer Science, vol.\u00a03383, pp.\u00a0425\u2013430, 2005). In this paper, we prove the bound \n\\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} \nis 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 \n\\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}\n. 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 \n\\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}\n, constructible in linear time, which is also optimal.",
"genre": "article",
"id": "sg:pub.10.1007/s10878-007-9119-8",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": [
{
"id": "sg:journal.1036683",
"issn": [
"1382-6905",
"1573-2886"
],
"name": "Journal of Combinatorial Optimization",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "4",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
}
],
"keywords": [
"time",
"length",
"results",
"height",
"products",
"triangulation",
"path",
"vertices",
"representation",
"paper",
"plane triangulations",
"triangulation G",
"graph G",
"linear time",
"plane graph G",
"plane triangulation G",
"visibility representation"
],
"name": "Optimal st-orientations for plane triangulations",
"pagination": "367-377",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1017605336"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s10878-007-9119-8"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s10878-007-9119-8",
"https://app.dimensions.ai/details/publication/pub.1017605336"
],
"sdDataset": "articles",
"sdDatePublished": "2021-11-01T18:10",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/article/article_432.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s10878-007-9119-8"
}
]

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/s10878-007-9119-8'

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/s10878-007-9119-8'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10878-007-9119-8'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10878-007-9119-8'

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

122 TRIPLES      22 PREDICATES      52 URIs      35 LITERALS      6 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0101
3 anzsrc-for:0102
4 anzsrc-for:0103
5 schema:author N4f49dcbba12d4d4ab995c99324e4e15a
6 schema:citation sg:pub.10.1007/11618058_32
7 sg:pub.10.1007/11786986_36
8 sg:pub.10.1007/978-3-540-31843-9_43
9 sg:pub.10.1007/bf00353652
10 sg:pub.10.1007/bf02187705
11 sg:pub.10.1007/bf02187706
12 sg:pub.10.1007/bf02253293
13 schema:datePublished 2007-11-22
14 schema:datePublishedReg 2007-11-22
15 schema:description Abstract For plane triangulations, 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 in the st-orientation 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} (Zhang and He in Lecture Notes in Computer Science, vol. 3383, pp. 425–430, 2005). 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.
16 schema:genre article
17 schema:inLanguage en
18 schema:isAccessibleForFree false
19 schema:isPartOf Nb3a829488b644c2392041144c3db3ebe
20 Nbb27bcb9584641748bb5ca8dbf92dac9
21 sg:journal.1036683
23 graph G
24 height
25 length
26 linear time
27 paper
28 path
29 plane graph G
30 plane triangulation G
31 plane triangulations
32 products
33 representation
34 results
35 time
36 triangulation
37 triangulation G
38 vertices
39 visibility representation
40 schema:name Optimal st-orientations for plane triangulations
41 schema:pagination 367-377
42 schema:productId N785c90919d9b4644b0090ee81a629eb1
43 N921b7c6ddafa4be69800ee377a587277
44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017605336
45 https://doi.org/10.1007/s10878-007-9119-8
46 schema:sdDatePublished 2021-11-01T18:10
48 schema:sdPublisher N9e1e8b54bf9b48aabc43b39a142e924f
49 schema:url https://doi.org/10.1007/s10878-007-9119-8
51 sgo:sdDataset articles
52 rdf:type schema:ScholarlyArticle
53 N03651452f18840c9b3a68910ca3764c0 rdf:first sg:person.011352641523.42
54 rdf:rest rdf:nil
55 N4f49dcbba12d4d4ab995c99324e4e15a rdf:first sg:person.012041227127.88
56 rdf:rest N03651452f18840c9b3a68910ca3764c0
57 N785c90919d9b4644b0090ee81a629eb1 schema:name doi
58 schema:value 10.1007/s10878-007-9119-8
59 rdf:type schema:PropertyValue
60 N921b7c6ddafa4be69800ee377a587277 schema:name dimensions_id
61 schema:value pub.1017605336
62 rdf:type schema:PropertyValue
63 N9e1e8b54bf9b48aabc43b39a142e924f schema:name Springer Nature - SN SciGraph project
64 rdf:type schema:Organization
65 Nb3a829488b644c2392041144c3db3ebe schema:issueNumber 4
66 rdf:type schema:PublicationIssue
68 rdf:type schema:PublicationVolume
69 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
70 schema:name Mathematical Sciences
71 rdf:type schema:DefinedTerm
72 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
73 schema:name Pure Mathematics
74 rdf:type schema:DefinedTerm
75 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
76 schema:name Applied Mathematics
77 rdf:type schema:DefinedTerm
78 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
79 schema:name Numerical and Computational Mathematics
80 rdf:type schema:DefinedTerm
81 sg:journal.1036683 schema:issn 1382-6905
82 1573-2886
83 schema:name Journal of Combinatorial Optimization
84 schema:publisher Springer Nature
85 rdf:type schema:Periodical
86 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
87 schema:familyName He
88 schema:givenName Xin
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
90 rdf:type schema:Person
91 sg:person.012041227127.88 schema:affiliation grid-institutes:grid.265893.3
92 schema:familyName Zhang
93 schema:givenName Huaming
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012041227127.88
95 rdf:type schema:Person
96 sg:pub.10.1007/11618058_32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033094987
97 https://doi.org/10.1007/11618058_32
98 rdf:type schema:CreativeWork
99 sg:pub.10.1007/11786986_36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017247286
100 https://doi.org/10.1007/11786986_36
101 rdf:type schema:CreativeWork
102 sg:pub.10.1007/978-3-540-31843-9_43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003846466
103 https://doi.org/10.1007/978-3-540-31843-9_43
104 rdf:type schema:CreativeWork
105 sg:pub.10.1007/bf00353652 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015637021
106 https://doi.org/10.1007/bf00353652
107 rdf:type schema:CreativeWork
108 sg:pub.10.1007/bf02187705 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027312329
109 https://doi.org/10.1007/bf02187705
110 rdf:type schema:CreativeWork
111 sg:pub.10.1007/bf02187706 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008881195
112 https://doi.org/10.1007/bf02187706
113 rdf:type schema:CreativeWork
114 sg:pub.10.1007/bf02253293 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018365863
115 https://doi.org/10.1007/bf02253293
116 rdf:type schema:CreativeWork
117 grid-institutes:grid.265893.3 schema:alternateName Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA
118 schema:name Computer Science Department, University of Alabama in Huntsville, 35899, Huntsville, AL, USA
119 rdf:type schema:Organization
120 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Buffalo, NY, USA
121 schema:name Department of Computer Science and Engineering, SUNY at Buffalo, 14260, Buffalo, NY, USA
122 rdf:type schema:Organization