An Algorithm for Finding Large Induced Planar Subgraphs

Edwards, Keith and Farr, Graham (2002) An Algorithm for Finding Large Induced Planar Subgraphs. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 75-83 (Official URL: http://dx.doi.org/10.1007/3-540-45848-4_6).

Full text not available from this repository.

Abstract

This paper presents an efficient algorithm that finds an induced planar subgraph of at least 3n/(d+1) vertices in a graph of n vertices and maximum degree d. This bound is sharp for d=3, in the sense that if \varepsilon>3/4 then there are graphs of maximum degree 3 with no induced planar subgraph of at least \varepsilon n vertices. Our performance ratios appear to be the best known for small d. For example, when d=3, our performance ratio of at least 3/4 compares with the ratio 1/2 obtained by Halldórsson and Lau. Our algorithm builds up an induced planar subgraph by iteratively adding a new vertex to it, or swapping a vertex in it with one outside it, in such a way that the procedure is guaranteed to stop, and so as to preserve certain properties that allow its performance to be analysed. This work is related to the authors' work on fragmentability of graphs.

Item Type:Conference Paper
Additional Information:10.1007/3-540-45848-4_6
Classifications:M Methods > M.600 Planar
G Algorithms and Complexity > G.999 Others
ID Code:422

Repository Staff Only: item control page

References

S. Bühler, Planarity of Graphs, M.Sc. dissertation, University of Dundee, 2000.

J. Cai and X. Han and R.E. Tarjan, An O(m log n)-Time Algorithm for the Maximal Planar Subgraph Problem, SIAM J. Comput. 22 (1993) 1142-1162.

G. Galinescu, C.G. Fernandes, U. Finkler, and H. Karloff, A better approximation algorithm for finding planar subgraphs, in: Proc. 7th ACM-SIAM Sympos. on Discrete Algorithms (Atlanta, GA, 1996); also: J. Algorithms 27 (1998) 269-302.

Robert Cimikowski, An Analysis of some heuristics for the maximum planar subgraph problem, in: Proc. 6th Ann. ACM-SIAM Symp. on Discrete Algorithms (San Francisco, CA, 1995), pp 332-331, ACM, New York, 1995.

G. Di Battista, Peter Eades, Roberto Tamassia and I. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 1999.

H.N. Djidjev and S.M. Venkatesan, Planarization of graphs embedded on surfaces, in: M. Nagel (ed.), Proc. 21st Internat. Workshop on Graph Theoretic-Concepts in Computer Science (WG '95) (Aachen, 1995), Lecture Notes in Comput. Sci., 1017, Springer, Berlin, 1995, pp. 62-72.

M.E. Dyer, L.R. Foulds and A.M. Frieze, Analysis of heuristics for finding a maximum weight planar subgraph, Eur. J. Operational Res. 20 (1985) 102-114.

K. Edwards and G. Farr, Fragmentability of graphs, J. Combin. Theory (Ser. B) 82 (2001) 30-37.

L. Faria, C.M.H. de Figueiredo and C.F.X. Mendonça, Splitting number is NP-complete, in: Juraj Hromkovic and Ondrej Sýkora (eds.), Proc. 24th Internat. Workshop on Graph-Theoretic Concepts in Computer Science (WG '98) (Smolenice Castle, Slovakia, 18-20 June 1998), Lecture Notes in Comput. Sci., 1517, Springer, 1998, pp. 285-297.

O. Goldschmidt and A. Takvorian, An efficient graph planarization two-phase heuristic, Networks 24 (1994) 69-73.

Magnús M. Halldórsson, Approximation of weighted independent set and hereditary subset problems, Journal of Graph Drawing Algorithms and Applications 4 (1) (2000) 1-16.

Magnús M. Halldórsson and Hoong Chuin Lau, Low-degree graph partitioning via local search with applications to constraint satisfaction, max cut, and coloring, Journal of Graph Drawing Algorithms and Applications 1 (3) (1997) 1-13.

J.P. Hutchinson, On genus-reducing and planarizing algorithms for embedded graphs, in: R.B. Richter (ed.) Graphs and Algorithms, Contemporary Mathematics 89, Amer. Math. Soc., Providence, RI, 1989.

Joan P. Hutchinson and Gary L. Miller, On deleting vertices to make a graph of positive genus planar, Discrete algorithms and complexity (Kyoto, 1986), Perspect. Comput.,15, pp. 81-98, Academic Press, Boston, MA, 1987.

M. Jünger and P. Mutzel, The polyhedral approach to the maximum planar subgraph problem: new chances for related problems, Graph Drawing '94, pp. 119-130.

M. Jünger and P. Mutzel, Maximum planar subgraphs and nice embeddings: practical layout tools. Algorithmica 16 (1996) 33-59.

P.C. Kainen, A generalization of the 5-color theorem, Proc. Amer. Math. Soc. 45 (1974) 450-453.

M.S. Krishnamoorthy and N. Deo, Node-deletion NP-complete problems, SIAM J. Comput. 8 (1979) 619-625.

J.M. Lewis and M. Yannakakis, The node-deletion problem for hereditary properties is NP-complete, J. Comput. System Sci. 20 (1980) 219-230.

Annegret Liebers, Planarizing graphs - a survey and annotated bibliography, Journal of Graph Algorithms and Applications 5 (1) (2001) 1-74.

P. C. Liu and R. C. Geldmacher. On the deletion of nonplanar edges of a graph. Proc. 10th. S-E Conf. Comb., Graph Theory, and Comp. 1977, Congressus Numerantium, No. 24 (1979) 727-738.

C. Lund and M. Yannakakis, The approximation of maximum subgraph problems, in: Proc. 20th Int. Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Comput. Sci., 700, Springer-Verlag, 1993, pp. 40-51.

P. Mutzel, The Maximum Planar Subgraph Problem, Ph.D. Thesis, Univ. zu Köln, 1994.