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 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
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

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{dbb56f29926a40adb6983486c4ec8421,

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

AN - SCOPUS:38149088136

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