Skip to Main content Skip to Navigation
Conference papers

Computing Boundary Cycle of a Pseudo-Triangle Polygon from Its Visibility Graph

Abstract : Visibility graph of a simple polygon is a graph with the same vertex set in which there is an edge between a pair of vertices if and only if the segment through them lies completely inside the polygon. Each pair of adjacent vertices on the boundary of the polygon are assumed to be visible. Therefore, the visibility graph of each polygon always contains its boundary edges. This implies that we have always a Hamiltonian cycle in a visibility graph which determines the order of vertices on the boundary of the corresponding polygon. In this paper, we propose a polynomial time algorithm for determining such a Hamiltonian cycle for a pseudo-triangle polygon from its visibility graph.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-03165378
Contributor : Hal Ifip <>
Submitted on : Wednesday, March 10, 2021 - 4:05:01 PM
Last modification on : Wednesday, March 10, 2021 - 4:15:02 PM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2023-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Hossein Boomari, Soheila Farokhi. Computing Boundary Cycle of a Pseudo-Triangle Polygon from Its Visibility Graph. 3rd International Conference on Topics in Theoretical Computer Science (TTCS), Jul 2020, Tehran, Iran. pp.61-71, ⟨10.1007/978-3-030-57852-7_5⟩. ⟨hal-03165378⟩

Share

Metrics

Record views

2