Logo

Login | Create Account

A Note on Computing a Maximal Planar Subgraph using PQ-Trees

Jünger, Michael and Leipert, Sebastian and Mutzel, Petra (1998) A Note on Computing a Maximal Planar Subgraph using PQ-Trees. [Preprint]

Full text available as:

[img]Postscript - Requires a viewer, such as GSview
99Kb

Abstract

The problem of computing a maximal planar subgraph of a non planar graph has been deeply investigated over the last 20 years. Several attempts have been tried to solve the problem with the help of PQ-trees. The latest attempt has been reported by Jayakumar et al. (1989). In this paper we show that the algorithm presented by Jayakumar et al. is not correct. We show that it does not necessarily compute a maximal planar subgraph and we note that the same holds for a modified version of the algorithm presented by Kant (1992). Our conclusions most likely suggest not to use PQ-trees at all for this specific problem.

Item Type:Preprint
Classifications:P Styles > P.540 Planar
G Algorithms and Complexity > G.840 Planarization
M Methods > M.700 Planarization-based
ID Code:19
Deposited By:GDEA, Administration
Deposited On:17 Jul 2003
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.zaik.uni-koeln.de/%7Epaper/preprints.html?show=zpr98-320

Repository Staff Only: item control page

References

Booth, K. and Lueker G. (1976) Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. Journal of Computer and System Sciences, 13 (1) 335-379.

Chai, J. and Han, X. and Tarjan, R. E. (1993) An O(mlogn)-time algorithm for the maximal planar subgraph problem. SIAM Journal of Comput., 22 1142-1162.

Chiba, T. and Nishioka, I. and Shirakawa, I. (1979) An algorithm for maximal planarization of graphs. In: Proceedings on the 1979 IEEE International Symposium on Circuits and Systems, pp. 336-441.

Di Battista, G. and Tamassia, R. (1989) Incremental planarity testing. In: Proceedings on the 30th Annual IEEE Symposium on Foundations of Computer Science, North Carolina, pp. 436-441.

Even, S. (1979) Graph Algorithms. Computer Science Press, Potomac, Maryland.

Even, S. and Tarjan, R. E. (1976) Computing and st-numbering. Theoretical Computer Science, 2 339-344.

Garey, M. R. and Johnson, D. S. (1979) Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman & Co., San Francisco.

Harary, F. (1969) Graph Theory, Addison Wesley.

Jayakumar, R. and Thulasiraman, K. and Swamy, M. N. S. (1986) On maximal planarization of non-planar graphs. IEEE Transactions on Circuits Systems, 33 (8) 843-844.

Jayakumar, R. and Thulasiraman, K. and Swamy, M. N. S. (1989) On O(n²)algorithms for graph planarization. IEEE Transactions on Computer-Aided Design, 8 (3) 257-267.

Jünger, M. and Leipert, S. and Mutzel, P. (1996) On computing a maximal planar subgraph using PQ-trees. Technical Report 96.227, Institut für Informatik, Universität zu Köln.

Kant, G. (1992) An O(n²) maximal planarization algorithm based on PQ-trees. Technical Report RUU-CS-92-03, Department of Computer Science, Utrecht University.

Leipert, S. (1995) Berechnung maximal planarer Untergraphen mit Hilfe von PQ-Bäumen. Master s thesis, Institut für Informatik der Universität zu Köln.

Lempel, A. and Even, S. and Cederbaum, I. (1967) An algorithm for planarity testing of graphs. In Theory of Graphs: International Symposium: Rome, July 1966, pp. 215-232. Gordon and Breach, New York, 1967.

Lengauer, T. (1990) Combinatorial Algorithms for Integrated Circuit Layout. Wiley.

Ozawa, T. and Takahashi, T. (1981) A graph-planarization algorithm and its application to random graphs. In Graph Theory and Algorithms, volume 108 of Lecture Notes in Computer Science, pp. 95-107.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.