Optimal st-orientations for plane triangulations

Huaming Zhang; Xin He

doi:10.1007/978-3-540-72870-2_28

Optimal st-orientations for plane triangulations

Huaming Zhang
, Xin He

Department of Computer Science and Engineering

University at Buffalo

University of Alabama in Huntsville

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

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 ≥ [2n/3] [18]. In this paper, we prove the bound 2n/3 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 2n/3 + O(1). 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 ≤ 2n/3 + O(1), constructible in linear time, which is also optimal.

Original language	English
Title of host publication	Algorithmic Aspects in Information and Management - Third International Conference, AAIM 2007, Proceedings
Publisher	Springer Verlag
Pages	296-305
Number of pages	10
ISBN (Print)	9783540728689
DOIs	https://doi.org/10.1007/978-3-540-72870-2_28
State	Published - 2007
Event	3rd International Conference on Algorithmic Aspects in Information and Management, AAIM 2007 - Portland, OR, United States Duration: Jun 6 2007 → Jun 8 2007

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4508 LNCS

Conference

Conference	3rd International Conference on Algorithmic Aspects in Information and Management, AAIM 2007
Country/Territory	United States
City	Portland, OR
Period	06/6/07 → 06/8/07

Access to Document

10.1007/978-3-540-72870-2_28

Cite this

Zhang, H., & He, X. (2007). Optimal st-orientations for plane triangulations. In Algorithmic Aspects in Information and Management - Third International Conference, AAIM 2007, Proceedings (pp. 296-305). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4508 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-72870-2_28

@inproceedings{ef418a93839844b39425e655e15b203e,

title = "Optimal st-orientations for plane triangulations",

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 ≥ [2n/3] [18]. In this paper, we prove the bound 2n/3 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 2n/3 + O(1). 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 ≤ 2n/3 + O(1), constructible in linear time, which is also optimal.",

author = "Huaming Zhang and Xin He",

year = "2007",

doi = "10.1007/978-3-540-72870-2\_28",

language = "English",

isbn = "9783540728689",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "296--305",

booktitle = "Algorithmic Aspects in Information and Management - Third International Conference, AAIM 2007, Proceedings",

address = "Germany",

note = "3rd International Conference on Algorithmic Aspects in Information and Management, AAIM 2007 ; Conference date: 06-06-2007 Through 08-06-2007",

}

Zhang, H & He, X 2007, Optimal st-orientations for plane triangulations. in Algorithmic Aspects in Information and Management - Third International Conference, AAIM 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4508 LNCS, Springer Verlag, pp. 296-305, 3rd International Conference on Algorithmic Aspects in Information and Management, AAIM 2007, Portland, OR, United States, 06/6/07. https://doi.org/10.1007/978-3-540-72870-2_28

Optimal st-orientations for plane triangulations. / Zhang, Huaming; He, Xin.
Algorithmic Aspects in Information and Management - Third International Conference, AAIM 2007, Proceedings. Springer Verlag, 2007. p. 296-305 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4508 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Optimal st-orientations for plane triangulations

AU - Zhang, Huaming

AU - He, Xin

PY - 2007

Y1 - 2007

N2 - 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 ≥ [2n/3] [18]. In this paper, we prove the bound 2n/3 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 2n/3 + O(1). 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 ≤ 2n/3 + O(1), constructible in linear time, which is also optimal.

AB - 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 ≥ [2n/3] [18]. In this paper, we prove the bound 2n/3 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 2n/3 + O(1). 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 ≤ 2n/3 + O(1), constructible in linear time, which is also optimal.

UR - https://www.scopus.com/pages/publications/38149088136

U2 - 10.1007/978-3-540-72870-2_28

DO - 10.1007/978-3-540-72870-2_28

M3 - Conference contribution

SN - 9783540728689

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 296

EP - 305

BT - Algorithmic Aspects in Information and Management - Third International Conference, AAIM 2007, Proceedings

PB - Springer Verlag

T2 - 3rd International Conference on Algorithmic Aspects in Information and Management, AAIM 2007

Y2 - 6 June 2007 through 8 June 2007

ER -

Zhang H, He X. Optimal st-orientations for plane triangulations. In Algorithmic Aspects in Information and Management - Third International Conference, AAIM 2007, Proceedings. Springer Verlag. 2007. p. 296-305. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-72870-2_28

Optimal st-orientations for plane triangulations

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this