Approximation algorithms for the maximum induced planar and outerplanar subgraph problems

被引：3
作者：
Morgan, Kerri [1 ]
Farr, Graham [1 ]
机构：
[1] Clayton School of Information Technology, Monash University
来源：
Journal of Graph Algorithms and Applications | 2007年 / 11卷 / 01期
关键词：
Graph theory;
D O I：
10.7155/jgaa.00141
中图分类号：
学科分类号：
摘要：
The task of finding the largest subset of vertices of a graph that induces a planar subgraph is known as the Maximum Induced Planar Subgraph problem (MIPS). In this paper, some new approximation algorithms for MIPS are introduced. The results of an extensive study of the performance of these and existing MIPS approximation algorithms on randomly generated graphs are presented. Efficient algorithms for finding large induced outerplanar graphs are also given. One of these algorithms is shown to find an induced outerplanar subgraph with at least 3n/(d + 5/3) vertices for graphs of n vertices with maximum degree at most d. The results presented in this paper indicate that most existing algorithms perform substantially better than the existing lower bounds indicate.
引用
收藏
页码：165 / 193
页数：28
相关论文
共 19 条
  • [1] Alon N., Mubayi D., Thomas R., Large induced forests in sparse graphs, J. Graph Theory, 38, pp. 113-123, (2001)
  • [2] Alon N., Spencer J., The Probabilistic Method, (1992)
  • [3] Bollobas B., A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, European J. Combin, 1, pp. 311-316, (1980)
  • [4] Di Battista G., Eades P., Tamassia R., Tollis I., Algorithms for drawing graphs: An annotated bibliography, Comput. Geom, 4, pp. 235-282, (1994)
  • [5] Di Battista G., Garg A., Liotta G., Tamassia R., Tassinari E., Vargiu F., An experimental comparison of four graph drawing algorithms, Comput. Geom, 7, pp. 303-325, (1997)
  • [6] Edwards K., Farr G., Fragmentability of graphs, J. Combin. Theory Ser. B, 82, pp. 30-37, (2001)
  • [7] Edwards K., Farr G., An algorithm for finding large induced planar subgraphs, Lecture Notes in Computer Science, 2265, pp. 75-83, (2002)
  • [8] Edwards K., Farr G., Planarization and fragmentability of some classes of graphs, (2003)
  • [9] Edwards K., Farr G., Planarization and fragmentability of some classes of graphs, Discrete Math
  • [10] Faria L., de Figueirdo C., Gravier S., Mendonca C., Stolfi J., Nonplanar vertex deletion: Maximum degree thresholds for NP/max SNP-hardness and a 3/4-approximation for finding maximum planar induced subgraphs, Electron. Notes Discrete Math, 18, pp. 121-126, (2004)
12