A Linear-Time Algorithm for Finding Induced Planar Subgraphs

Huang, S, Bao, Z, Culpepper, S, Zhang, P and Zhang, B 2018, 'A Linear-Time Algorithm for Finding Induced Planar Subgraphs', in Proceedings of 17th International Symposium on Experimental Algorithms (SEA 2018), L'Aquila, Italy, 27-29 June 2018, pp. 1-15.


Document type: Conference Paper
Collection: Conference Papers

Title A Linear-Time Algorithm for Finding Induced Planar Subgraphs
Author(s) Huang, S
Bao, Z
Culpepper, S
Zhang, P
Zhang, B
Year 2018
Conference name SEA 2018
Conference location L'Aquila, Italy
Conference dates 27-29 June 2018
Proceedings title Proceedings of 17th International Symposium on Experimental Algorithms (SEA 2018)
Publisher Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Place of publication Dagstuhl, Germany
Start page 1
End page 15
Total pages 15
Abstract In this paper we study the problem of efficiently and effectively extracting induced planar subgraphs. Edwards and Farr proposed an algorithm with O(mn) time complexity to find an induced planar subgraph of at least 3n/(d+1) vertices in a graph of maximum degree d. They also proposed an alternative algorithm with O(mn) time complexity to find an induced planar subgraph graph of at least 3n/(bar{d}+1) vertices, where bar{d} is the average degree of the graph. These two methods appear to be best known when d and bar{d} are small. Unfortunately, they sacrifice accuracy for lower time complexity by using indirect indicators of planarity. A limitation of those approaches is that the algorithms do not implicitly test for planarity, and the additional costs of this test can be significant in large graphs. In contrast, we propose a linear-time algorithm that finds an induced planar subgraph of n-nu vertices in a graph of n vertices, where nu denotes the total number of vertices shared by the detected Kuratowski subdivisions. An added benefit of our approach is that we are able to detect when a graph is planar, and terminate the reduction. The resulting planar subgraphs also do not have any rigid constraints on the maximum degree of the induced subgraph. The experiment results show that our method achieves better performance than current methods on graphs with small skewness.
Subjects Database Management
Keyword(s) induced planar subgraphs
experimental analysis
DOI - identifier 10.4230/LIPIcs.SEA.2018.23
Copyright notice © Shixun Huang, Zhifeng Bao, J. Shane Culpepper, Ping Zhang, and Bang Zhang; licensed under Creative Commons License CC-BY
ISBN 9783959770705
Versions
Version Filter Type
Altmetric details:
Access Statistics: 14 Abstract Views  -  Detailed Statistics
Created: Thu, 21 Feb 2019, 12:10:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us