A note on computing a maximal planar subgraph using PQ-trees

Jünger, Michael; Leipert, Sebastian; Mutzel, Petra

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

報告書

A note on computing a maximal planar subgraph using PQ-trees

MPS-Authors

/persons/resource/persons44906

Leipert, Sebastian
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45092

Mutzel, Petra
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

MPI-I-98-1-008.pdf
(全文テキスト（全般）), 454KB

付随資料 (公開)

There is no public supplementary material available

引用

Jünger, M., Leipert, S., & Mutzel, P.(1998). A note on computing a maximal planar subgraph using PQ-trees (MPI-I-1998-1-008). Saarbrücken: Max-Planck-Institut für Informatik.

引用: https://hdl.handle.net/11858/00-001M-0000-0014-7BDC-4

要旨

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. [10]. 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 [12]. Our conclusions most likely suggest not to use PQ-trees at all for this specific problem.