Testing Outerplanarity of Bounded Degree Graphs
Testing Outerplanarity of Bounded Degree Graphs
复制标题
DOI：
10.1007/s00453-014-9897-1
复制
发表时间：
2010-09
期刊：
影响因子：
1.1
通讯作者：
Yuichi Yoshida;Hiro Ito
中科院分区：
文献类型：
--
作者：
Yuichi Yoshida;Hiro Ito
We present an efficient algorithm for testing outerplanarity of graphs in the bounded-degree model. In this model, given a graphwith degree bound, we should distinguish with high probability the case thatis outerplanar from the case that modifying at least an-fraction of the edge set is necessary to makeouterplanar. Our algorithm runs in time polynomial inandonly. To achieve the time complexity, we exploit the tree-like structure inherent to an outerplanar graph using the microtree/macrotree decomposition of a tree. As a corollary, we show that the property of being a cactus is testable in time polynomial inand.
