Header menu link for other important links
X
A local characterization for perfect plane near-triangulations
S. M. Salam, , K. Murali Krishnan
Published in Elsevier B.V.
2020
Volume: 840
   
Pages: 45 - 58
Abstract
We derive a local criterion for a plane near-triangulated graph to be perfect. It is shown that a plane near-triangulated graph is perfect if and only if it does not contain either a vertex, an edge or a triangle, the neighbourhood of which has an odd hole as its boundary. The characterization leads to an O(n2) algorithm for checking perfectness of plane near-triangulations. © 2020 Elsevier B.V.
About the journal
JournalData powered by TypesetTheoretical Computer Science
PublisherData powered by TypesetElsevier B.V.
ISSN03043975